Vraag Wat betekent O (log n) precies?


Ik ben momenteel bezig met het leren van Big O Notation-looptijden en afgeschreven tijden. Ik begrijp de notie van Op) lineaire tijd, wat betekent dat de grootte van de invoer de groei van het algoritme proportioneel beïnvloedt ... en hetzelfde geldt voor bijvoorbeeld kwadratische tijd Op2) enz. zelfs algoritmen, zoals permutatie-generatoren, met Op!) tijden, die groeien door faculteiten.

De volgende functie is bijvoorbeeld Op) omdat het algoritme evenredig groeit met zijn invoer n:

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

Evenzo, als er een geneste lus was, zou de tijd O (n2).

Maar wat is het precies O (log n)? Wat betekent het bijvoorbeeld om te zeggen dat de hoogte van een volledige binaire boom is O (log n)?

Ik weet (misschien niet tot in detail) wat Logaritme is, in die zin: log10 100 = 2, maar ik kan niet begrijpen hoe ik een functie kan identificeren met een logaritmische tijd.


1732
2018-02-21 20:05


oorsprong


antwoorden:


Ik kan niet begrijpen hoe ik een functie kan identificeren met een logtijd.

De meest voorkomende kenmerken van de logaritmische looptijdfunctie zijn:

  • de keuze van het volgende element waarop een actie moet worden uitgevoerd, is een van de vele mogelijkheden, en
  • er zal er maar één gekozen moeten worden.

of

  • de elementen waarop de actie wordt uitgevoerd, zijn cijfers van n

Dit is de reden waarom het opzoeken van mensen in een telefoonboek O (log n) is. U hoeft niet te controleren elk persoon in het telefoonboek om de juiste te vinden; in plaats daarvan kun je eenvoudigweg delen en te veroveren door te kijken op basis van waar hun naam alfabetisch is, en in elke sectie hoef je alleen maar een deel van elke sectie te verkennen voordat je uiteindelijk iemands telefoonnummer vindt.

Natuurlijk duurt een groter telefoonboek nog steeds langer, maar het groeit niet zo snel als de proportionele toename in de extra grootte.


We kunnen het telefoonboekvoorbeeld uitbreiden om andere soorten bewerkingen te vergelijken en hun looptijd. We gaan ervan uit dat ons telefoonboek dat heeft gedaan ondernemingen (de "Gouden Gids") met unieke namen en mensen (de "White Pages") die mogelijk geen unieke namen hebben. Een telefoonnummer is toegewezen aan maximaal één persoon of bedrijf. We gaan er ook van uit dat het constant duurt om naar een specifieke pagina te gaan.

Dit zijn de looptijden van bepaalde bewerkingen die we in het telefoonboek kunnen uitvoeren, van beste naar slechtste:

  • O (1) (beste geval): Gezien de pagina waarop de naam van een bedrijf staat en de bedrijfsnaam, vind je het telefoonnummer.

  • O (1) (gemiddelde situatie): Gezien de pagina waarop de naam van een persoon staat en hun naam, vind je het telefoonnummer.

  • O (log n): Geef, op basis van de naam van een persoon, het telefoonnummer op door een willekeurig punt halverwege het deel van het boek dat u nog niet hebt gezocht, te selecteren en controleer vervolgens of de naam van de persoon op dat moment staat. Herhaal vervolgens het proces ongeveer halverwege het deel van het boek waar de naam van de persoon ligt. (Dit is een binaire zoekopdracht naar de naam van een persoon.)

  • Op): Zoek alle personen wiens telefoonnummers het cijfer "5" bevatten.

  • Op): Ga naar een telefoonnummer en zoek de persoon of het bedrijf met dat nummer.

  • O (n log n): Er was een warboel op het kantoor van de drukker en in ons telefoonboek werden alle pagina's in een willekeurige volgorde ingevoegd. Corrigeer de bestelling zodat deze correct is door naar de voornaam op elke pagina te kijken en die pagina vervolgens op de juiste plek in een nieuw, leeg telefoonboek te plaatsen.

Voor de onderstaande voorbeelden zijn we nu op het kantoor van de printer. Telefoonboeken wachten om naar elke bewoner of elk bedrijf te worden verzonden en er staat een sticker op elk telefoonboek die aangeeft waar deze naartoe moet worden verzonden. Elke persoon of bedrijf krijgt één telefoonboek.

  • O (n log n): We willen het telefoonboek personaliseren, dus we gaan de naam van elke persoon of bedrijf in hun aangewezen exemplaar vinden, omcirkelen vervolgens hun naam in het boek en schrijven een kort bedankbriefje voor hun beschermheerschap.

  • Op2): Er is een fout opgetreden op kantoor en elke invoer in elk van de telefoonboeken heeft een extra "0" aan het einde van het telefoonnummer. Neem wat white-out en verwijder elke nul.

  • O (n · n!): We zijn klaar om de telefoonboeken in het verzenddok te laden. Helaas is de robot die de boeken moest laden, in de war geraakt: hij plaatst de boeken in een willekeurige volgorde in de vrachtwagen! Erger nog, het laadt alle boeken op de vrachtwagen, controleert vervolgens of ze in de juiste volgorde staan ​​en zo niet, dan worden ze leeggemaakt en begint het opnieuw. (Dit is de gevreesde bogo sorteren.)

  • Opn): U repareert de robot zodat deze de dingen correct laadt. De volgende dag speelt een van je collega's een grap tegen je en brengt de robot van het laadplatform in contact met de geautomatiseerde printsystemen. Telkens wanneer de robot een origineel boek gaat laden, maakt de fabrieksprinter een duplicaat van alle telefoonboeken! Gelukkig zijn de bugdetectiesystemen van de robot zo geavanceerd dat de robot niet probeert nog meer exemplaren af ​​te drukken wanneer het een dubbel boek voor het laden tegenkomt, maar het moet nog steeds elk origineel en dubbel boek dat is afgedrukt, laden.


2177
2018-02-21 20:14



Er zijn al veel goede antwoorden op deze vraag geplaatst, maar ik geloof dat we echt een belangrijke missen, namelijk het geïllustreerde antwoord.

Wat betekent het om te zeggen dat de hoogte van een volledige binaire boom O is (log n)?

De volgende tekening toont een binaire boom. Merk op hoe elk niveau het dubbele aantal knopen bevat ten opzichte van het niveau erboven (vandaar binair):

Binary tree

Binair zoeken is een voorbeeld met complexiteit O(log n). Laten we zeggen dat de knooppunten op het onderste niveau van de structuur in figuur 1 artikelen in een gesorteerde verzameling vertegenwoordigen. Binair zoeken is een algoritme om te delen en te veroveren, en de tekening laat zien hoe we (maximaal) 4 vergelijkingen nodig hebben om het record te vinden waarnaar we op zoek zijn in deze 16-artikeldataset.

Stel dat we in plaats daarvan een dataset hadden met 32 ​​elementen. Ga door met de bovenstaande tekening om te ontdekken dat we nu 5 vergelijkingen nodig hebben om te vinden waar we naar op zoek zijn, omdat de boom maar één niveau dieper is geworden toen we de hoeveelheid gegevens vermenigvuldigden. Dientengevolge kan de complexiteit van het algoritme worden beschreven als een logaritmische volgorde.

plotten log(n) op een gewoon stuk papier, resulteert in een grafiek waarin de opkomst van de curve afneemt als n toeneemt:

O(log n)


509
2018-02-21 22:22



O(log N) eigenlijk betekent dat de tijd lineair stijgt, terwijl de n gaat exponentieel omhoog. Dus als het duurt 1 tweede om te berekenen 10 elementen, het zal duren 2 seconden om te berekenen 100 elementen, 3 seconden om te berekenen 1000 elementen, enzovoort.

Het is O(log n) wanneer we het soort algoritmen verdelen en verslaan, bijvoorbeeld binair zoeken. Een ander voorbeeld is snel sorteren, waarbij we elke keer de array verdelen in twee delen en elke keer dat het duurt O(N) tijd om een ​​spilelement te vinden. Vandaar het N O(log N) 


463
2018-02-21 20:18



De onderstaande uitleg gebruikt het geval van een volledig evenwichtige binaire structuur om u te helpen begrijpen hoe we logaritmische tijdcomplexiteit krijgen.

Binaire structuur is een geval waarbij een probleem van grootte n is verdeeld in een subprobleem van grootte n / 2 totdat we een probleem van grootte 1 bereiken:

height of a binary tree

En zo krijg je O (log n), wat de hoeveelheid werk is die moet worden gedaan in de boomstructuur hierboven om tot een oplossing te komen.

Een algemeen algoritme met O (log n) tijdcomplexiteit is Binair zoeken, waarvan de recursieve relatie T (n / 2) + O (1) is, d.w.z. op elk volgend niveau van de boom splitst u het probleem op in de helft en doet u constant extra werk.


196
2017-10-26 19:33



Als u een functie had die het volgende doet:

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2**n elements.

Dan duurt het log2(n) tijd. De Big O-notatie, losjes gezegd, betekent dat de relatie alleen waar hoeft te zijn voor grote n, en dat constante factoren en kleinere termen kunnen worden genegeerd.


120
2018-02-21 20:11



Overzicht

Anderen hebben goede diagramvoorbeelden gegeven, zoals de boomdiagrammen. Ik heb geen eenvoudige codevoorbeelden gezien. Dus naast mijn uitleg, zal ik sommige algoritmen voorzien van eenvoudige printinstructies om de complexiteit van verschillende algoritmecategorieën te illustreren.

Eerst wil je een algemeen idee hebben van Logaritme, waar je uit kunt komen https://en.wikipedia.org/wiki/Logarithm . Gebruik van natuurwetenschap e en het natuurlijke logboek. Engineering disciples gebruiken log_10 (log base 10) en computerwetenschappers zullen log_2 (log base 2) veel gebruiken, aangezien computers binair gebaseerd zijn. Soms zie je afkortingen van natuurlijk logboek als ln(), ingenieurs laten de _10 normaal gesproken staan ​​en gebruiken ze gewoon log() en log_2 wordt afgekort als lg(). Alle typen logaritmen groeien op dezelfde manier, daarom delen ze dezelfde categorie log(n).

Als je de onderstaande codevoorbeelden bekijkt, raad ik aan naar O (1), dan O (n) en vervolgens O (n ^ 2) te kijken. Als je daar goed mee bent, kijk dan naar de anderen. Ik heb zowel schone voorbeelden als varianten opgenomen om aan te tonen hoe subtiele wijzigingen nog steeds in dezelfde indeling kunnen resulteren.

U kunt denken aan O (1), O (n), O (logn), enz. Als klassen of categorieën van groei. Sommige categorieën hebben meer tijd nodig om te doen dan andere. Deze categorieën helpen ons een manier te vinden om de prestaties van het algoritme te bestellen. Sommige groeiden sneller omdat de input n groeit. In de volgende tabel wordt de groei numeriek weergegeven. Ga in de onderstaande tabel naar log (n) als het maximum van log_2.

enter image description here

Eenvoudige codevoorbeelden van verschillende Big O-categorieën:

O (1) - voorbeelden van constante tijd:

  • Algoritme 1:

Algoritme 1 drukt eenmaal hallo en is niet afhankelijk van n, dus het zal altijd in constante tijd worden uitgevoerd, dus dat is het ook O(1).

print "hello";
  • Algoritme 2:

Algoritme 2 drukt driemaal hallo, maar het is niet afhankelijk van een invoerformaat. Zelfs als n groeit, zal dit algoritme altijd maar drie keer hallo drukken. Dat gezegd hebbende 3, is een constante, dus dit algoritme is ook O(1).

print "hello";
print "hello";
print "hello";

O (log (n)) - Logaritmische voorbeelden:

  • Algoritme 3 - Dit gedraagt ​​zich als "log_2"

Algoritme 3 toont een algoritme dat wordt uitgevoerd in log_2 (n). Merk op dat de post-operatie van de for-lus de huidige waarde van i met 2 vermenigvuldigt, dus i gaat van 1 naar 2 naar 4 naar 8 naar 16 naar 32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";
  • Algoritme 4 - Dit gedraagt ​​zich als "log_3"

Algoritme 4 demonstreert log_3. Merk op i gaat van 1 naar 3 naar 9 naar 27 ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";
  • Algoritme 5 - Dit gedraagt ​​zich als "log_1.02"

Algoritme 5 is belangrijk, omdat het helpt aantonen dat, zolang het getal groter is dan 1 en het resultaat herhaaldelijk wordt vermenigvuldigd met zichzelf, u kijkt naar een logaritmisch algoritme.

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O (n) - Voorbeelden van lineaire tijden:

  • Algoritme 6

Dit algoritme is eenvoudig, dat n keer op dezelfde manier wordt afgedrukt.

for(int i = 0; i < n; i++)
  print "hello";
  • Algoritme 7

Dit algoritme toont een variatie, waarbij het hallo n / 2 keer wordt afgedrukt. n / 2 = 1/2 * n. We negeren de 1/2 constante en zien dat dit algoritme O (n) is.

for(int i = 0; i < n; i = i + 2)
  print "hello";

O (n * log (n)) - nlog (n) Voorbeelden:

  • Algoritme 8

Zie dit als een combinatie van O(log(n)) en O(n). Het nesten van de for-lussen helpt ons om de O(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";
  • Algoritme 9

Algoritme 9 lijkt op algoritme 8, maar elk van de lussen heeft variaties mogelijk gemaakt, wat er nog steeds in resulteert dat het eindresultaat is O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O (n ^ 2) - n kwadraat Voorbeelden:

  • Algoritme 10

O(n^2) wordt eenvoudig verkregen door geneste standaard voor lussen.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";
  • Algoritme 11

Zoals algoritme 10, maar met enkele variaties.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O (n ^ 3) - n gekubde voorbeelden:

  • Algoritme 12

Dit is vergelijkbaar met algoritme 10, maar met 3 lussen in plaats van 2.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";
  • Algoritme 13

Zoals algoritme 12, maar met enkele variaties die nog steeds opbrengen O(n^3).

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

Overzicht

Het bovenstaande geeft een aantal ongecompliceerde voorbeelden en variaties om te helpen aantonen welke subtiele veranderingen kunnen worden geïntroduceerd die de analyse echt niet veranderen. Hopelijk geeft het je voldoende inzicht.


107
2018-04-26 22:50



Logaritmische looptijd (O(log n)) betekent in wezen dat de looptijd toeneemt in verhouding tot de logaritme van de input-grootte - als bijvoorbeeld 10 items hooguit een bepaalde hoeveelheid tijd in beslag nemen x, en 100 items zijn hooguit, laten we zeggen, 2xen 10.000 items zijn hooguit 4x, dan ziet het eruit als een O(log n) tijd complexiteit.


84
2018-02-21 20:10