Exemples d'algorithmes présentant des complexités O(1), O(n log n) et O(log n)

Question

Quels sont certains algorithmes que nous utilisons quotidiennement et qui présentent des complexités O(1), O(n log n) et O(log n) ?

Answer 1

Un exemple simple de O(1) pourrait être return 23; -- quelle que soit l'entrée, cela reviendra dans un temps fixe et fini.

Un exemple typique de O(N log N) serait de trier un tableau d'entrée avec un bon algorithme (par exemple mergesort).

Un exemple typique si O(log N) recherchait une valeur dans un tableau d'entrée trié par bissection.

Answer 2

O(1) : trouver le meilleur prochain coup à Chess (ou Go d'ailleurs). Comme le nombre d'états de jeu est fini, ce n'est que O(1) :-)