Available inFrenchEnglishGermanHindiPortugueseRussianSpanish
Big-O et structures de données pour entretiens
Donnez le coût en temps et en mémoire de n'importe quelle opération sur un tableau, une liste chaînée, une table de hachage, un arbre, un tas ou un trie, cas amorti compris, et défendez-le à l'oral. Pour qui prépare un entretien de code ou un examen de structures de données, connaît les boucles et le hachage, mais n'a encore fait que reconnaître une réponse en Big-O. Cinquante-quatre cartes en sept chapitres ; les patterns algorithmiques relèvent de Coding Interview Patterns.
Un programme en n^2 met 1 seconde sur 1 000 éléments. Estimez son temps sur 2 000 éléments.
Environ 4 secondes
— Doublez l'entrée, puis élevez ce facteur au carré.
Source
Doubler n multiplie un coût quadratique par quatre, puisque (2n)^2 = 4n^2 : dix fois plus d'entrée, cent fois plus de travail. Ce rapport répond à « et si les données grossissent ? » sans connaître la moindre constante, ni la vitesse de la machine, seulement la forme de la croissance. Comparez avec d'autres croissances : sur une routine en O(n log n), doubler n fait un peu plus que doubler le temps ; en O(log n), cela ajoute une étape.