Berechnung der zeitlichen Komplexität, wenn die Anzahl der Elemente im Algorithmus nicht gegeben ist - Algorithmus, Rekursion, Komplexitätstheorie, Zeitkomplexität, Wiederholung

Ich möchte die Daten an der "Position von Ende in einer verknüpften Liste finden. Ich habe diesen Code mit Rekursion geschrieben:

KNOCHENSTRUKTUR:

struct Node
{
int data;
struct Node * next;
}

CODE:

int i = 10;

int find ( Node * ptr, unsigned int count )
{
if( nullptr == ptr )
{
++ count;
return count;
}

count = find ( ptr->next , count );
if( i == count )
{
std::cout << "Successful here: " << ptr->data << std::endl;
exit ( -1 ) ;
}

else
{
++ count;
return count ;
}
}

Ich habe Grundidee über das Berechnen von Zeitkomplexitäten unter Verwendung von Wiederholungsrelationen. Aber ich bin nicht in der Lage, die Beziehung selbst zu schreiben. Kann jemand eine Richtung geben?

Von dem, was ich verstehe, teile ich das Problem jedesmal auf weniger Elemente auf (indem ich zum nächsten Knoten übergehe).

Es sollte also so etwas sein

T (n) = T (n-1) + Konstante

Könnte die Tree-Methode oder eine andere Methode in einer solchen Situation besser sein?

Antworten:

0 für die Antwort № 1

Es ist ziemlich einfach.

Sie haben bereits die Reihenfolge für Ihre zeitliche Komplexität mit

T(n) = T(n-1) + Constant

Was Sie auch brauchen, sind Ihre Endbedingung. Das erste ist das Element n. Die zweite ist, dass Ihr Array nur m Element hat, wobei m <n ist.

Also seit deinem count Für jede Iteration erhöht sich die Zeitkomplexitätsfolge etwas

T(i,c) = T(i-c, c+1) + Constant

Dies liegt daran, dass Sie i zum Index erklärt haben, den Sie finden möchten.

So können wir jetzt für die erste Endbedingung schreiben

T(0,i) = Constant

Und für die zweite Endbedingung ist genau das gleiche wie T(m,0) Wenn ich also> m bin, wechseln wir einfach zu m für die Komplexität.

Nehmen wir jetzt an, dass Constant gleich 1 ist.

Dann erhalten wir die folgende Gleichung

T(i,0) = T(i-0,1) +1 = T(i-1,2) +2 = T(i-2,3) +3 = T(i-3,4) +4 = .... = i+1

Also die Komplexität ist T((min(i,m),0) = i+1 oder T(i,0) ist in O(i).

Sie könnten Ihren Code in ändern

int find ( Node * ptr, unsigned int i ){
if( nullptr == ptr )
return i;

if( i == 0 )
{
std::cout << "Successful here: " << ptr->data << std::endl;
return 0;
}
return find ( ptr->next , --count );
}

So hättest du dann die Sequenz T(n) = T(n-1) + Constant

---