Mon doute est que je ne comprends pas quelle propriété ou comment ils prennent en commun dans la ligne no. 3
Quelqu'un peut-il expliquer dans un langage simple?
3 Réponses :
C'est juste par définition de la notation big-O: O (log n - loglog n) = O (log n) (En fait, ça devrait être gros-Thêta ici).
Sir In 3ème ligne après O (n / logn log (n / logn)).
La deuxième partie de la troisième ligne n'est qu'une explication, pas une partie d'expression
Il ne s'agit pas de prendre du commun, dans "[longn - loglogn = O (logn)]" ils ont en fait expliqué la logique, cette partie est distincte de l'expression d'origine.
Je pense qu'ils ont essayé d'écrire de cette manière, "[O (logn - loglogn) = O (logn)]"
Je suppose que ce serait peut-être plus simple que ça:
n numéros peuvent être triés dans n log n de temps. n de temps. Ce serait alors aussi simple que:
Votre méthode obtient le bon résultat, mais elle suppose que n log n échelles linéairement avec n (ce qui n'est pas le cas). Si vous utilisez votre méthode pour un algorithme O (n ^ 2), vous obtenez n / X = n ^ 2 / n => X = 1 (plutôt que le bon X = sqrt (n)).