Obliczanie złożoności czasu, gdy liczba elementów nie jest podana w algorytmie - algorytm, rekurencja, teoria złożoności, złożoność czasowa, powtarzalność

Chcę znaleźć dane na i-tej pozycji od końca na liście połączonej. Napisałem ten kod za pomocą rekursji:

STRUKTURA WĘZŁA:

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

KOD :

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 ;
}
}

Mam podstawowe pojęcie na temat obliczania złożoności czasu za pomocą relacji cyklicznych. Ale nie jestem w stanie sam napisać relacji. Czy ktoś może wskazać kierunek?

Z tego co rozumiem, dzielę problem na mniej elementów za każdym razem (przechodząc do następnego węzła).

Tak powinno być coś w stylu

T (n) = T (n-1) + Stała

Czy metoda Tree czy jakakolwiek inna metoda mogłaby być lepsza w takiej sytuacji?

Odpowiedzi:

0 dla odpowiedzi № 1

To dość proste.

Masz już sekwencję złożoności czasu

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

To, czego potrzebujesz, to twój warunek końcowy. Pierwszy to element n. Druga to twoja tablica ma tylko element m, gdzie m <n.

Od twojego count rośnie dla każdej iteracji musimy nieco zmienić kolejność złożoności czasu

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

To dlatego, że zadeklarowałeś, że chcesz być indeksem, który chcesz znaleźć.

Więc teraz dla pierwszego warunku końcowego możemy napisać

T(0,i) = Constant

A dla drugiego końca warunek jest dokładnie taki sam jak T(m,0) więc jeśli i> m po prostu przełączymy i na m dla złożoności.

Teraz przyjmijmy, że Stała jest równa 1.

Otrzymujemy następujące równanie

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

Tak więc złożoność jest T((min(i,m),0) = i+1 lub T(i,0) jest w O(i).

Możesz zmienić swój kod na

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 );
}

Więc będziesz miał kolejność T(n) = T(n-1) + Constant

---