Verschil tussen O(n) en O(log(n)) – wat is beter en wat is O(log(n)) precies?

Dit is mijn eerste cursus in datastructuren en bij elke lezing / TA-lezing hebben we het over O(log(n)). Dit is waarschijnlijk een domme vraag, maar ik zou het op prijs stellen als iemand me kan uitleggen wat het precies betekent!?


Antwoord 1, autoriteit 100%

Het betekent dat het ding in kwestie (meestal lopende tijd) schaalt op een manier die consistent is met de logaritme van de invoergrootte.

Big-O-notatiebetekent niet een exactevergelijking , maar eerder een gebonden. De uitvoer van de volgende functies is bijvoorbeeld allemaal O(n):

f(x) = 3x
g(x) = 0.5x
m(x) = x + 5

Omdat als je x verhoogt, hun outputs allemaal lineair toenemen – als er een 6:1 verhouding is tussen f(n)en g(n), zal er ook een verhouding van ongeveer 6:1 zijn tussen f(10*n)en g(10*n)enzovoort.


Over de vraag of O(n)of O(log n)beter is, overweeg dan: als n = 1000, dan log n = 3(voor log-base-10). Welk algoritme zou je liever laten uitvoeren: 1000 seconden of 3 seconden?


Antwoord 2, autoriteit 32%

Voor het korte antwoord: O(log n) is beter dan O(n)

Wat is nu precies O( log n) ?

Over het algemeen verwijst log nnaar de logaritme met grondtal-2, (op dezelfde manier waarop lnde logaritmen met grondtal e vertegenwoordigt). Deze logaritme met grondtal 2 is de inverse van een exponentiële functie.
Een exponentiële functie groeitzeer snel en we kunnen intuïtief afleiden dat de inverse functie precies het tegenovergestelde zal doen, d.w.z. groeitheel langzaam.

Bijvoorbeeld

x = O(log n)

We kunnen n voorstellen als ,

n= 2x

En

210= 1024 → lg(1024) = 10

220= 1.048.576 → lg(1048576) = 20

230= 1.073.741.824 → lg(1073741824) = 30

Grote verhogingen in nleiden slechts tot een zeer kleine verhoging van log(n)

Voor een complexiteit van O(n) daarentegen krijgen we een lineaire relatie

Een factor log2n moet altijd worden overgenomen met een factor n.

Om dit verder te verstevigen, kwam ik een voorbeeld tegen in Algoritmes ontgrendeld door Thomas Cormen

Beschouw 2 computers: A en B

Beide computers hebben de taak om in een array naar een waarde te zoeken
Laten we aannemen dat de arrays 10 miljoen elementen bevatten om door te zoeken

Computer A- Deze computer kan 1 miljard instructies per seconde uitvoeren en zal naar verwachting de bovenstaande taak uitvoeren met een algoritme met een complexiteit van O(n). We kunnen de tijd die deze computer nodig heeft om de taak te voltooien schatten als

n/(instructies p seconde) → 107/10^9 = 0,01 seconden

Computer B- Deze computer is veel langzamer en kan slechts 10 miljoen instructies per seconde uitvoeren. Van computer B wordt verwacht dat hij de bovenstaande taak uitvoert met behulp van een algoritme met een complexiteit van O(log n). We kunnen de tijd die deze computer nodig heeft om de taak te voltooien schatten als

log(n) /(instructies p seconde) → log(107)/107= 0.0000002325349

Met deze illustratie kunnen we zien dat hoewel computer A veel beter is dan computer B, dankzij het algoritme dat door B wordt gebruikt, de taak veel sneller wordt voltooid.

Ik denk dat het nu heel duidelijk moet zijn waarom O(log(n)) veel sneller is dan O(n)


Antwoord 3, autoriteit 17%

Voor de invoer van maat nzal een algoritme van O(n)stappen uitvoeren die evenredig zijn aan n, terwijl een ander algoritme van O(log(n))voert stappen ongeveer log(n)uit.

Het is duidelijk dat log(n)kleiner is dan nen daarom is het complexiteitsalgoritme O(log(n))beter. Omdat het veel sneller zal zijn.


Antwoord 4, autoriteit 5%

http://en.wikipedia.org/wiki/Big_oh

O(log n) is beter.


Antwoord 5, autoriteit 5%

O(logn) betekent dat de maximale looptijd van het algoritme evenredig is met de logaritme van de invoergrootte.
O(n) betekent dat de maximale looptijd van het algoritme evenredig is met de invoergrootte.

in principe is O(iets) een bovengrens voor het aantal instructies van het algoritme (atomaire). daarom is O(logn) strakker dan O(n) en is het ook beter in termen van algoritmeanalyse. Maar alle algoritmen die O(logn) zijn, zijn ook O(n), maar niet omgekeerd…


Antwoord 6, autoriteit 3%

Formele definitie:

g(x) = O(f(x)) <=> er is x0 en constante C dat voor elke x > x0, |g(x)| <= C|f(x)|.

Dus als je algoritme A voor probleem P vindt waarvan de complexiteit O(f(n)),
je kunt zeggen dat het aantal stappen dat je algoritme zal doen, asymptotisch lager of gelijk is aan f(n), terwijl n meestal de invoergrootte is. (n kan van alles zijn)

Voor meer informatie: http://en.wikipedia.org/wiki/Big_O_notation.

Other episodes