Calcul de la complexité temporelle lorsque le nombre d'éléments n'est pas indiqué dans l'algorithme - algorithme, récursivité, théorie de la complexité, complexité temporelle, récurrence

Je veux trouver les données à la "position" de la fin dans une liste chaînée. J'ai écrit ce code en utilisant la récursivité:

STRUCTURE DE NOEUD:

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

J'ai une idée de base sur le calcul des complexités temporelles à l'aide de relations de récurrence. Mais je ne suis pas capable d'écrire la relation elle-même. Quelqu'un peut-il donner une direction?

De ce que je comprends, je divise le problème en un élément de moins à chaque fois (en passant au nœud suivant).

Donc ça devrait être quelque chose comme

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

La méthode Tree ou toute autre méthode pourrait-elle être meilleure dans une telle situation?

Réponses:

0 pour la réponse № 1

C'est assez simple.

Vous avez déjà la séquence pour votre complexité temporelle avec

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

Vous avez également besoin de votre condition finale. La première est que vous trouvez l'élément n. La seconde est que votre tableau n'a que m élément où m <n.

Donc depuis votre count augmente pour chaque itération, nous devons changer la séquence de complexité de temps un peu à

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

C'est parce que vous avez déclaré que j'étais l'index que vous voulez trouver.

Alors maintenant, pour la première condition de fin, nous pouvons écrire

T(0,i) = Constant

Et pour la seconde condition, la condition est exactement la même que T(m,0) Donc, si je m, nous basculons simplement sur m pour la complexité.

Supposons maintenant que Constant est égal à 1.

Ensuite, nous obtenons l'équation suivante

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

Donc, la complexité est T((min(i,m),0) = i+1 ou T(i,0) est dans O(i).

Vous pouvez changer votre code en

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

Donc, vous auriez alors la séquence T(n) = T(n-1) + Constant

---