La détermination de la complexité dans le pire cas d'un algorithme

Question

Quelqu'un peut-il s'il vous plaît me expliquer comment on peut déterminer la complexité dans le pire cas d'un algorithme. Je sais que nous devons l'utiliser le W équation (n) = max {t (I) | élément I de D), où D est l'ensemble des entrées de taille n. Est-ce que je calcule le nombre d'opérations effectuées pour chaque élément I et puis prendre son maximum? Quel moyen plus facile est là pour y arriver?

Answer 1

A partir de l'équation est de penser un peu en arrière. Qu'est-ce que vous vous souciez vraiment est l'évolutivité, ou, ce qui est ce que ça va faire comme vous augmentez la taille de l'entrée.

Si vous avez juste une boucle, par exemple, vous avez une complexité O (n) algorithme. Si vous avez une boucle dans une autre bien, il devient O (n ^ 2), parce qu'il doit maintenant faire n ^ 2 beaucoup de choses pour toute entrée taille n.

Quand vous parlez pire des cas, vous parlez en général sur les algorithmes non déterministes, où vous pourriez avoir une boucle qui peut arrêter prématurément. Ce que vous voulez faire pour cela est supposer le pire et faire semblant de la boucle s'arrêtera le plus tard possible. Donc, si nous avons:

  

for (int i = 0; i 0,5) j = n;      }   }

Nous dirions que le pire cas est O (n ^ 2). Même si nous savons qu'il est très probable que la boucle moyenne éclatera tôt, nous recherchons la pire performance possible.

Answer 2

Cette équation est plus d'une définition qu'un algorithme.

Est-ce que l'algorithme dans les soins de question sur autre chose que la taille de son entrée? Sinon, le calcul W (n) est "facile".

Le cas échéant, essayez de trouver une entrée pathologique. Par exemple, avec quicksort il pourrait être assez évident qu'une entrée est pathologique triée, et vous pouvez faire un peu de comptage pour voir qu'il faut O (n ^ 2) étapes. À ce moment-là, vous pouvez soit

1. Argue que votre entrée est "au maximum" pathologique
2. présentent une correspondance limite supérieure du temps d'exécution sur toute entrée

Exemple de # 1:

  

Chaque passage de quicksort mettra le pivot au bon endroit, et récursif puis sur les deux parties. ( Alerte handwave ) Le pire des cas est d'avoir le reste du tableau d'un côté du pivot. Une entrée triée y parvient.

Exemple de # 2:

  

Chaque passe de tri rapide met le pivot à la bonne place, donc il n'y a pas plus de O (n) passe. Chaque passe ne nécessite pas plus que le travail O (n). En tant que tel, aucune entrée peut provoquer le tri rapide de prendre plus de O (n ^ 2).

Dans ce cas, # 2 est beaucoup plus facile.