Comptage du nombre d'étapes de codes (complexité temporelle)

Question

J'ai besoin d'aide pour compter le nombre d'étapes concernant la complexité temporelle des fragments de code.

total = 0 
    i = 0 
while i<3: 
    j=0 
    while j<3: 
     total = total + 1 
     j = j+1 
    i = i+1 
return total 

j'ai la solution déclarant: 2 + 3 * (2 + 3 * 3 + 2) +2 = 43

les deux premières lignes de la partie supérieure où totale = 0 et i = 0, oui je sais que chacun d'eux est 1 pas de temps chaque donc additionnant me donne 2. pour la déclaration de temps, je ne suis pas sûr de savoir comment il a obtenu, mais depuis que je < 3, son pas de temps 3? et alors j = 0 est 1 pas de temps.

Maintenant, voici où je ne comprends pas tout à fait. s'il y a une boucle i et j imbriquée, comment puis-je déterminer la complexité temporelle? dans la solution, je remarque qu'il y a * (multiple) et j'apprécierai si quelqu'un pourrait le décomposer en termes plus simples pour moi.

Answer 1

La complexité temporelle prend un argument. Par exemple, O (n^2). Comme il est écrit, je ne sais pas quelle partie de votre fonction changerait, donc c'est juste constant, O (1).

Disons que la chose que i est comparée à, 3 dans ce cas, est ce qui peut changer. Comme votre fonction est "faire un j-chose trois fois pour chaque je." Dans ce cas, vous verrez que si vous augmentez cette variable, vous ajouterez trois étapes supplémentaires à la boucle. Cela signifie que la complexité ressemblerait à O (3n). Puisque nous pouvons supprimer des multiples constants, c'est juste O (n). Ce que je viens d'écrire est hypothétique, cependant. Cela dépend de ce qui varie dans votre fonction.