Big O Log résoudre des problèmes

Question

J'ai une question qui vient d'un livre d'algorithmes que je suis en train de lire et je suis perplexe sur la façon de le résoudre (cela fait longtemps que je n'ai pas fait de log ou exposant). Le problème est le suivant:

Supposons que nous comparions des implémentations de tri par insertion et de tri par fusion sur la même machine . Pour les entrées de taille n, le tri par insertion s'exécute en 8n^2 étapes, tandis que le tri par fusion s'exécute en 64n étapes de log n. Pour quelles valeurs de n le tri par insertion bat-il le tri par fusion? Log est la base 2. J'ai commencé à essayer de résoudre pour l'égalité, mais rester coincé n = 8 log n.

Je voudrais la réponse pour discuter de la façon de résoudre cela mathématiquement (force brute avec excel pas admissible désolé;)). Tous les liens vers la description des mathématiques de notation seraient très utiles dans ma compréhension de votre réponse.

Merci d'avance!

Answer 1

http://www.wolframalpha.com/input/?i=solve%288+log%282%2Cn%29%3Dn%2Cn%29 (édité depuis ancien lien a cessé de travailler)

Answer 2

Votre meilleur pari est d'utiliser la méthode de Newton.

http://en.wikipedia.org/wiki/Newton%27s_method

Answer 3

Une technique pour résoudre ce serait de saisir simplement une calculatrice graphique et graphique les deux fonctions (voir le lien Wolfram dans une autre réponse). Trouvez l'intersection qui vous intéresse (au cas où il y aurait plusieurs intersections, comme dans votre exemple).

Dans tous les cas, il n'y a pas d'expression simple pour résoudre n = 8 log₂ n (pour autant que je sache). Il peut être plus simple de reformuler la question comme suit: "Trouvez un zéro de f (n) = n - 8 log₂ n". Tout d'abord, trouvez une région contenant l'intersection qui vous intéresse et continuez de réduire cette région. Par exemple, supposons que vous savez que votre cible n est supérieure à 42, mais inférieure à 44. f (42) est inférieur à 0 et f (44) est supérieur à 0. Essayez f (43). C'est moins de 0, alors essayez 43.5. Il est toujours inférieur à 0, alors essayez 43.75. Il est supérieur à 0, alors essayez 43.625. C'est plus grand que 0, alors continuez à descendre, et ainsi de suite. Cette technique est appelée binary search.

Désolé, c'est juste une variation de "force brute avec Excel" :-)

Edit:

Pour le plaisir, j'ai fait une feuille de calcul qui permet de résoudre ce problème avec la recherche binaire: binary‑search.xls. La logique de recherche binaire est dans la deuxième colonne de données, et je l'ai simplement auto-étendu.