Ik kwam net rond deze rare ontdekking, in normale wiskunde zou n*logn kleiner zijn dan n, omdat log n meestal kleiner is dan 1.
Dus waarom is O(nlog(n)) groter dan O(n)? (dwz waarom wordt aangenomen dat nlogn meer tijd kost dan n)
Volgt Big-O een ander systeem?
Antwoord 1, autoriteit 100%
Het bleek dat ik Logn verkeerd begreep als minder dan 1.
Zoals ik enkele van mijn senioren heb gevraagd, heb ik dit vandaag zelf leren kennen, dat als de waarde van n groot is (wat meestal het geval is, wanneer we Big O beschouwen, dwz in het slechtste geval), logn groter kan zijn dan 1.
Dus ja,
O(1) < O(log) < O(n) < O(nlogn) geldt.
(Ik dacht dat dit een domme vraag was en stond op het punt het ook te verwijderen, maar realiseerde me toen dat geen enkele vraag een domme vraag is en dat er misschien anderen zijn die deze verwarring begrijpen, dus ik heb het hier achtergelaten.)
Antwoord 2, autoriteit 36%
…omdat log n altijd kleiner is dan 1.
Dit is een onjuist uitgangspunt. Logbn> 1 voor alle n> b. Bijvoorbeeld log232 = 5.
In de omgangstaal kun je log nzien als het aantal cijfers in n. Als neen 8-cijferig getal is, log dan n≈ 8. Logaritmen zijn meestalgroter dan 1 voor de meeste waarden van n, omdat de meestegetallen meerdere cijfers hebben.
Antwoord 3, autoriteit 15%
Plot beide grafieken( op desmos (https://www.desmos.com/calculator) of een ander web) en kijk zelf naar het resultaat op grote waarden van n ( y=f(n)). Ik zeg dat je moet zoeken naar een grote waarde, want voor een kleine waarde van n heeft het programma geen tijdsprobleem. Voor het gemak had ik hieronder een grafiek bijgevoegd die je kunt proberen voor een andere basis van log.
Het rood staat voor tijd = n en blauw staat voor tijd = nlog(n).
Antwoord 4, autoriteit 6%
Log(n) kan groter zijn dan 1 als n groter is dan b. Maar dit is geen antwoord op uw vraag waarom O(n*logn) groter is dan O(n).
Meestal is het grondtal kleiner dan 4. Dus voor hogere waarden n wordt n*log(n) groter dan n. En daarom O(nlogn) > O(n).
Antwoord 5, autoriteit 4%
Deze grafiek kan helpen. log (n) stijgt sneller dan n en is groter dan 1 voor n groter dan het grondtal van logaritme. https://stackoverflow.com/a/7830804/11617347
Antwoord 6, autoriteit 4%
In computers is dat log grondtal 2 en niet grondtal 10. Dus log(2) is 1 en log(n), waarbij n>2, is een positief getal dat groter is dan 1.
Alleen in het geval van log (1) hebben we de waarde kleiner dan 1, anders is het groter dan 1.
Antwoord 7, autoriteit 2%
Het maakt niet uit hoe twee functies zich gedragen bij een kleine waarde van n, ze worden met elkaar vergeleken wanneer ngroot genoeg is. Theoretisch is er een nzodanig dat voor elke gegeven n > N, dan nlogn >= n. Als je N=10kiest, is nlognaltijd groter dan n.
Antwoord 8
Voor hogere waarden van log n wordt het groter dan 1. aangezien we alle mogelijke waarden van n beschouwen, kunnen we zeggen dat log n meestal groter is dan 1. Daarom kunnen we zeggen O(nlogn) > O(n) (uitgaande van hogere waarden)