Comment caractériseriez-vous ce qui suit en notation big-O?Quelle est la fonction de coût big-O de cet algorithme?
rotors = [1,2,3,4,5 ...]
widgets = ['a', 'b', 'c', 'd', 'e' ...]
assert len(rotors) == len(widgets)
for r in rotors:
for w in widgets:
...
del widgets[0]
C'est O (n^2). Vous pouvez voir que le nombre d'exécutions en boucle interne est:
n + (n - 1) + (n - 2) + ... + 1
parce qu'un widget est supprimé chaque itération de boucle externe. C'est (n^2 + n)/2, qui est O (n^2).
puisque vous passez par les deux boucles c'est O (n^2).
C'est un argument trop simpliste. Mais il arrive que ce soit correct dans ce cas. – polygenelubricants
bien je ne vois pas pourquoi compliquer les choses :)) ce n'est pas comme s'il nous a donné un algorithme complet ... –
Cet algorithme aura la pire performance de O (n^2).
Cet argument est défectueux en général. Vous pouvez avoir des boucles imbriquées qui sont 'O (N)', et cela peut aussi être 'O (2^N)'. Cela dépend vraiment de l'algorithme lui-même, pas seulement de l'imbrication structurelle. – polygenelubricants
Yah, tu as raison. Je n'ai pas pensé ça tout le long. Mis à jour :) –
En fait, étant donné l'assertion initiale, le meilleur des cas est O (n^2). Si la boucle interne fait quelque chose de plus que O (1), ce n'est certainement pas le pire des cas. – andand
En raison de l'affirmation:
assert len(rotors) == len(widgets)
les réponses de O (n) sont corrects, mais dans le cas général où les listes ne sont pas nécessairement la même longueur, vous appelez cela O (m * n).
+1 pour frapper sur l'importance de l'hypothèse de len (rotors) == len (widgets) –
C'est O (n^2), mais je pense que les gens manquent la partie delete de cette question. Vous pourriez penser que vous abaissez le Big-O mais tout ce que vous faites est de multiplier le coefficient par 1/2. Ceci est dû au fait que n + (n-1) + ... + 2 + 1 = n (n + 1)/2. Comme N va à l'infini il devient n^2/2 qui est juste O (n^2)
Au risque d'être à la fois contraire et pédant, vous n'avez pas vraiment fourni assez d'informations pour répondre à la question en général termes. Certes, la performance n'est pas meilleure que O (n^2), mais puisque vous ne donnez aucun détail sur ce que vous faites dans la boucle interne, ce sera en général bien pire. Cependant, en supposant que ce qui se passe dans la boucle interne est O (1), alors la performance globale est O (n^2).
Je ne pouvais pas être plus d'accord. – redtuna
Oui, c'est pourquoi ces gros problèmes O sont toujours difficiles à comprendre. Mais si je devais deviner je dirais O (n^2) puisque vous passez par 2 pour les boucles effectuant une opération à chaque fois.
voulez-vous dire del w [0] ou del widgets [0]? C'est-à-dire que vous supprimez le premier widget pour chaque r dans les rotors, ou le premier élément de chaque widget (auquel cas l'indentation serait fausse?) Ou quoi? – Francesco