Wat betekent O(log n) precies?

Ik ben aan het leren over de looptijden en afgeschreven tijden van Big O Notation. Ik begrijp het begrip O(n) 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 O(n²) enz..zelfs algoritmen, zoals permutatiegeneratoren, met O(n!) tijden, die met faculteiten groeien.

De volgende functie is bijvoorbeeld O(n) omdat het algoritme groeit in verhouding tot de invoer n:

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

Als er een geneste lus zou zijn, zou de tijd O(n²) zijn.

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

Ik weet wel (misschien niet tot in detail) wat logaritme is, in de zin dat: log₁₀ 100 = 2, maar ik begrijp niet hoe ik een functie met een logaritmische tijd kan identificeren.

---

Antwoord 1, autoriteit 100%

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

De meest voorkomende kenmerken van de logaritmische looptijdfunctie zijn dat:

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

of

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

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

Natuurlijk kost een groter telefoonboek nog steeds meer tijd, maar het zal niet zo snel groeien als de proportionele toename van de extra grootte.

---

We kunnen het voorbeeld van het telefoonboek uitbreiden om andere soorten bewerkingen en hun looptijd te vergelijken. We gaan ervan uit dat ons telefoonboek bedrijven (de “Gele Pagina’s”) heeft die unieke namen hebben en mensen (de “Witte Gids”) die mogelijk geen unieke namen hebben. Een telefoonnummer wordt aan maximaal één persoon of bedrijf toegekend. We gaan er ook van uit dat het constant tijd kost om naar een specifieke pagina te bladeren.

Hier zijn de looptijden van sommige bewerkingen die we in het telefoonboek kunnen uitvoeren, van snelst tot langzaamst:

• O(1) (in het ergste geval): Zoek het telefoonnummer op de pagina waarop de naam van een bedrijf staat en de bedrijfsnaam.

• O(1) (in het gemiddelde geval): Zoek het telefoonnummer op, gezien de pagina waarop de naam van een persoon staat en hun naam.

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

• O(n): Vind alle mensen van wie het telefoonnummer het cijfer “5” bevat.

• O(n): Geef een telefoonnummer op, zoek de persoon of het bedrijf met dat nummer.

• O(n log n): Er was een misverstand op het kantoor van de drukker en in ons telefoonboek waren alle pagina’s in willekeurige volgorde ingevoegd. Pas de volgorde aan 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 drukker. Telefoonboeken wachten om naar elke bewoner of elk bedrijf te worden gemaild, en er is een sticker op elk telefoonboek die aangeeft waar het naartoe moet worden gemaild. Elke persoon of elk bedrijf krijgt één telefoonboek.

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

• O(n²): Er is een fout opgetreden op kantoor en elke vermelding in elk van de telefoonboeken heeft een extra “0” aan de einde van het telefoonnummer. Neem wat wit weg en verwijder elke nul.

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

• O(nⁿ): Je repareert de robot zodat deze dingen correct laadt. De volgende dag haalt een van je collega’s een grap met je uit en verbindt de laaddokrobot met de geautomatiseerde printsystemen. Elke keer dat de robot een origineel boek gaat laden, maakt de fabrieksprinter een kopie van alle telefoonboeken! Gelukkig zijn de bugdetectiesystemen van de robot zo geavanceerd dat de robot niet nog meer exemplaren probeert af te drukken wanneer hij een duplicaatboek tegenkomt om te laden, maar hij moet nog steeds elk origineel en duplicaat dat is afgedrukt, laden.

---

Antwoord 2, autoriteit 25%

O(log n) betekent in feite dat de tijd lineair stijgt terwijl de n exponentieel stijgt. Dus als het 1 seconde kost om 10 elementen te berekenen, duurt het 2 seconden om 100 elementen te berekenen, 3 seconden om 1000 elementen te berekenen, enzovoort.

?Het is O(log n) als we algoritmen van het verdeel-en-heers-type gebruiken, bijvoorbeeld binair zoeken. Een ander voorbeeld is snel sorteren, waarbij we de array elke keer in twee delen verdelen en elke keer dat het O(n) tijd kost om een ​​pivot-element te vinden. Vandaar dat het N O(log N)

---

Antwoord 3, autoriteit 20%

Er zijn al veel goede antwoorden op deze vraag gepost, 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(log n) is?

De volgende tekening toont een binaire boom. Merk op hoe elk niveau het dubbele aantal knooppunten bevat in vergelijking met het bovenstaande niveau (vandaar binair):

Binair zoeken is een voorbeeld met complexiteit O(log n). Laten we zeggen dat de knooppunten in het onderste niveau van de boom in figuur 1 items in een gesorteerde verzameling vertegenwoordigen. Binair zoeken is een verdeel-en-heers-algoritme, en de tekening laat zien hoe we (maximaal) 4 vergelijkingen nodig hebben om het record te vinden waarnaar we zoeken in deze dataset met 16 items.

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 wat we zoeken, omdat de boom slechts één niveau dieper is geworden toen we de hoeveelheid gegevens vermenigvuldigden. Als gevolg hiervan kan de complexiteit van het algoritme worden beschreven als een logaritmische volgorde.

Het uitzetten van log(n) op een gewoon stuk papier, resulteert in een grafiek waarin de stijging van de curve vertraagt ​​naarmate n toeneemt:

---

Antwoord 4, autoriteit 9%

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

Binaire boom is een geval waarin een probleem van grootte n wordt verdeeld in een deelprobleem van grootte n/2 totdat we een probleem van grootte 1 bereiken:

En zo krijg je O(log n), wat de hoeveelheid werk is die aan de bovenstaande boom moet worden gedaan 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, dwz op elk volgend niveau van de boom verdeel je het probleem in tweeën en doe je een constante hoeveelheid extra werk.

---

Antwoord 5, autoriteit 8%

Overzicht

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

Ten eerste wil je een algemeen idee hebben van logaritme, dat je kunt vinden op https://en.wikipedia. org/wiki/Logaritme . Natuurwetenschappen gebruiken e en het natuurlijke logboek. Technische discipelen zullen log_10 (log base 10) gebruiken en computerwetenschappers zullen log_2 (log base 2) veel gebruiken, aangezien computers binair zijn. Soms zie je afkortingen van natuurlijke log als ln(), ingenieurs laten de _10 normaal gesproken weg en gebruiken gewoon log() en log_2 wordt afgekort als lg(). Alle soorten logaritmen groeien op dezelfde manier, daarom delen ze dezelfde categorie van log(n).

Als je de onderstaande codevoorbeelden bekijkt, raad ik aan om naar O(1) te kijken, dan naar O(n) en dan naar O(n^2). Als je daar goed mee bent, kijk dan naar de anderen. Ik heb duidelijke voorbeelden en variaties toegevoegd om te laten zien hoe subtiele veranderingen nog steeds kunnen resulteren in dezelfde categorisering.

Je kunt O(1), O(n), O(logn), enz. zien als klassen of categorieën van groei. Sommige categorieën zullen meer tijd in beslag nemen dan andere. Deze categorieën geven ons een manier om de prestaties van het algoritme te ordenen. Sommige groeiden sneller naarmate de invoer n groeit. De volgende tabel toont deze groei numeriek. Denk in de onderstaande tabel aan log(n) als het plafond van log_2.

Eenvoudige codevoorbeelden van verschillende Big O-categorieën:

O(1) – Voorbeelden van constante tijd:

• Algoritme 1:

Algoritme 1 drukt hallo één keer af en het is niet afhankelijk van n, dus het zal altijd in constante tijd draaien, dus het is O(1).

print "hello";

• Algoritme 2:

Algoritme 2 drukt hallo 3 keer af, maar is niet afhankelijk van een invoergrootte. Zelfs als n groeit, zal dit algoritme altijd maar 3 keer hallo afdrukken. 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 werkt als “log_2”

Algoritme 3 demonstreert een algoritme dat wordt uitgevoerd in log_2(n). Merk op dat de nabewerking 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 werkt als “log_3”

Algoritme 4 demonstreert log_3. Let 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 werkt als “log_1.02”

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

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

O(n) – Voorbeelden van lineaire tijd:

• Algoritme 6

Dit algoritme is eenvoudig en drukt hallo-tijden af.

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 de O(n*log(n))

te verkrijgen

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

• Algoritme 9

Algoritme 9 is als algoritme 8, maar elk van de lussen heeft variaties toegestaan, wat nog steeds resulteert in het eindresultaat 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 standaard for-lussen te nesten.

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 in blokjes Voorbeelden:

• Algoritme 12

Dit is als 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 O(n^3) opleveren.

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";

Samenvatting

Het bovenstaande geeft een aantal duidelijke voorbeelden en variaties om te laten zien welke subtiele veranderingen kunnen worden aangebracht die de analyse niet veranderen. Hopelijk geeft het je genoeg inzicht.

---

Antwoord 6, autoriteit 5%

Als je een functie had die duurt:

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 log₂(n) tijd. De Big O-notatie betekent, losjes gesproken, dat de relatie alleen waar hoeft te zijn voor grote n, en dat constante factoren en kleinere termen kunnen worden genegeerd.

---

Antwoord 7, autoriteit 4%

De logaritme

Ok, laten we proberen volledig te begrijpen wat een logaritme eigenlijk is.

Stel je voor dat we een touw hebben en dat hebben we aan een paard vastgemaakt. Als het touw direct aan het paard is vastgemaakt, is de kracht die het paard zou moeten wegtrekken (bijvoorbeeld van een man) direct 1.

Stel je nu voor dat het touw om een ​​paal is gelust. Het paard om weg te komen zal nu vele malen harder moeten trekken. Het aantal keren hangt af van de ruwheid van het touw en de grootte van de paal, maar laten we aannemen dat het iemands kracht met 10 zal vermenigvuldigen (wanneer het touw een volledige draai maakt).

Als het touw nu eenmaal wordt gelust, moet het paard 10 keer harder trekken. Als de mens besluit het paard echt moeilijk te maken, mag hij het touw opnieuw om een ​​paal lussen, waardoor de kracht nog eens 10 keer toeneemt. Een derde lus zal de kracht opnieuw met nog eens 10 keer verhogen.

We kunnen zien dat voor elke lus de waarde met 10 toeneemt. Het aantal beurten dat nodig is om een ​​willekeurig getal te krijgen, wordt de logaritme van het getal genoemd, dwz we hebben 3 berichten nodig om je sterkte met 1000 keer te vermenigvuldigen, 6 berichten om te vermenigvuldigen uw kracht met 1.000.000.

3 is de logaritme van 1000 en 6 is de logaritme van 1.000.000 (grondtal 10).

Dus wat betekent O(log n) eigenlijk?

In ons voorbeeld hierboven is onze ‘groeisnelheid’ O(log n). Voor elke extra lus is de kracht die ons touw aankan 10 keer groter:

Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n

Het bovenstaande voorbeeld gebruikte wel grondtal 10, maar gelukkig is de grondtal van het logboek onbelangrijk als we het hebben over de grote o-notatie.

Stel je nu voor dat je een getal tussen 1-100 probeert te raden.

Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!  

Je moest nu zeven keer raden om dit goed te krijgen. Maar wat is hier de relatie? Wat is het meeste aantal items dat je kunt raden van elke extra gok?

Guesses | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024

Aan de hand van de grafiek kunnen we zien dat als we een binaire zoekopdracht gebruiken om een ​​getal tussen 1-100 te raden, we maximaal 7 pogingen nodig hebben. Als we 128 getallen hadden, zouden we het getal ook in 7 pogingen kunnen raden, maar voor 129 getallen zijn maximaal 8 pogingen nodig (in relatie tot logaritmen zouden we hier 7 keer moeten raden voor een waardebereik van 128, 10 keer raden voor een waardebereik van 1024. 7 is de logaritme van 128, 10 is de logaritme van 1024 (grondtal 2).

Merk op dat ik ‘maximaal’ vet heb gemaakt. Big-O-notatie verwijst altijd naar het ergste geval. Als je geluk hebt, kun je het getal in één poging raden en dus is het beste geval O(1), maar dat is een ander verhaal.

We kunnen zien dat voor elke gok onze dataset kleiner wordt. Een goede vuistregel om te bepalen of een algoritme een logaritmische tijd heeft, is:
om te zien of de dataset na elke iteratie in een bepaalde volgorde krimpt

Hoe zit het met O(n log n)?

Uiteindelijk kom je een lineair-itmisch tijdsalgoritme O(n log(n)) tegen. De vuistregel hierboven is weer van toepassing, maar deze keer moet de logaritmische functie n keer worden uitgevoerd, b.v. het verkleinen van een lijst n keer, wat voorkomt in algoritmen zoals een mergesort.

Je kunt gemakkelijk zien of de algoritmische tijd n log n is. Zoek naar een buitenste lus die door een lijst (O(n)) loopt. Kijk dan of er een binnenlus is. Als de binnenste lus knipt/verkleint de dataset bij elke iteratie, is die lus (O(log n)), en dus is het algemene algoritme = O(n log n).

Disclaimer: het voorbeeld van een touw-logaritme is overgenomen uit de uitstekende Mathematician’s Delight boek van W.Sawyer.

---

Antwoord 8, autoriteit 3%

Logaritmische looptijd (O(log n)) betekent in wezen dat de looptijd groeit in verhouding tot de logaritme van de invoergrootte – bijvoorbeeld als 10 items duren maximaal X, en 100 items duren maximaal 2x, en 10.000 items duren maximaal 4x, dan ziet het eruit als een O(log n) tijdcomplexiteit.

---

Antwoord 9, autoriteit 2%

Ik raad je aan eerst het volgende boek te lezen;

Algoritmen (4e editie)

Hier zijn enkele functies en hun verwachte complexiteit. Cijfers geven uitvoeringsfrequenties van instructies aan.

Volgende Big-O Complexity Chart ook overgenomen van bigocheatsheet

Ten slotte is er een heel eenvoudige showcase die laat zien hoe het wordt berekend;

Anatomie van de uitvoeringsfrequenties van een programma.

De looptijd van een programma analyseren (voorbeeld).

---

Antwoord 10, autoriteit 2%

Je kunt O(log N) intuïtief bedenken door te zeggen dat de tijd evenredig is met het aantal cijfers in N.

Als een bewerking constant tijdwerk uitvoert op elk cijfer of bit van een invoer, duurt de hele bewerking evenredig met het aantal cijfers of bits in de invoer, niet de grootte van de invoer; dus O(log N) in plaats van O(N).

Als een bewerking een reeks constante tijdbeslissingen neemt die elk de grootte van de te beschouwen invoer halveren (verkleint met een factor 3, 4, 5..), zal het geheel tijd kosten die evenredig is met logbase 2 (grondtal 3, grondtal 4, grondtal 5…) van de grootte N van de invoer, in plaats van O(N).

Enzovoort.

---

Antwoord 11, autoriteit 2%

De beste manier waarop ik altijd een algoritme moest visualiseren dat in O(log n) draait, is als volgt:

Als u de probleemomvang met een vermenigvuldigingsbedrag vergroot (d.w.z. de grootte vermenigvuldigt met 10), wordt het werk alleen verhoogd met een optelsom.

Als je dit toepast op je binaire boomvraag, zodat je een goede toepassing hebt: als je het aantal knooppunten in een binaire boom verdubbelt, neemt de hoogte slechts met 1 toe (een additief bedrag). Als je het nog een keer verdubbelt, is het nog steeds maar met 1 toegenomen (ik ga er natuurlijk van uit dat het in evenwicht blijft en zo). Op die manier doe je, in plaats van je werk te verdubbelen wanneer de probleemomvang wordt vermenigvuldigd, maar heel weinig meer werk. Daarom zijn O(log n)-algoritmen geweldig.

---

Antwoord 12, autoriteit 2%

Wat is log_b(n)?

Het is het aantal keren dat u een stam met lengte n herhaaldelijk in b gelijke delen kunt knippen voordat u een sectie van maat 1 bereikt.

---

Antwoord 13

Verdeel en heers-algoritmen hebben meestal een logn-component voor de looptijd. Dit komt door het herhaaldelijk halveren van de invoer.

In het geval van binair zoeken, gooit u bij elke iteratie de helft van de invoer weg. Opgemerkt moet worden dat log in Big-O-notatie log basis 2 is.

Bewerken: zoals opgemerkt, maakt de log-basis niet uit, maar bij het afleiden van de Big-O-prestaties van een algoritme, zal de log-factor afkomstig zijn van de halvering, vandaar dat ik het beschouw als basis 2.

---

Antwoord 14

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

Ik zou dit herformuleren als ‘hoogte van een complete binaire boom is log n’. Het berekenen van de hoogte van een volledige binaire boom zou O(log n) zijn, als je stap voor stap naar beneden zou gaan.

Ik begrijp niet hoe ik een functie kan identificeren met een logaritmische
tijd.

Logaritme is in wezen het omgekeerde van machtsverheffen. Dus als elke ‘stap’ van uw functie een factor van elementen uit de originele itemset elimineert, is dat een logaritmisch tijdalgoritme.

Voor het boomvoorbeeld kun je gemakkelijk zien dat het verlagen van een niveau van knooppunten een exponentieel aantal elementen vermindert terwijl je doorgaat. Het populaire voorbeeld van het doorzoeken van een op naam gesorteerd telefoonboek is in wezen gelijk aan het doorlopen van een binaire zoekboom (de middelste pagina is het hoofdelement en u kunt bij elke stap afleiden of u naar links of naar rechts wilt gaan).

---

Antwoord 15

O(log n) is een beetje misleidend, meer precies is het O(log₂ n), d.w.z. (logaritme met grondtal 2).

De hoogte van een gebalanceerde binaire boom is O(log₂ n), aangezien elk knooppunt twee (let op de “twee” zoals in log₂ n) kind heeft knooppunten. Een boom met n knopen heeft dus een hoogte van log₂ n.

Een ander voorbeeld is binair zoeken, met een looptijd van O(log₂ n) omdat je bij elke stap de zoekruimte door 2 deelt.

---

Antwoord 16

Deze 2 gevallen nemen O(log n) tijd in beslag

case 1: f(int n) {
      int i;
      for (i = 1; i < n; i=i*2)
        printf("%d", i);
    }
 case 2  : f(int n) {
      int i;
      for (i = n; i>=1 ; i=i/2)
        printf("%d", i);
    }

---

Antwoord 17

Het betekent simpelweg dat de tijd die nodig is voor deze taak toeneemt met log(n) (voorbeeld: 2s voor n = 10, 4s voor n = 100, …). Lees de Wikipedia-artikelen over Binair zoekalgoritme en Big O-notatie voor meer precisie.

---

Antwoord 18

O(log n) verwijst naar een functie (of algoritme, of stap in een algoritme) die werkt in een hoeveelheid tijd die evenredig is aan de logaritme (meestal grondtal 2 in de meeste gevallen, maar niet altijd , en in ieder geval is dit niet significant door de grote O-notatie*) van de grootte van de invoer.

De logaritmische functie is de inverse van de exponentiële functie. Anders gezegd, als je invoer exponentieel groeit (in plaats van lineair, zoals je normaal zou denken), groeit je functie lineair.

O(log n) looptijden zijn heel gebruikelijk in elke soort verdeel-en-heers-toepassing, omdat u (idealiter) het werk elke keer halveert. Als u in elk van de stappen van deling of verovering constant tijdwerk doet (of werk dat geen constante tijd is, maar waarbij de tijd langzamer groeit dan O(log n)), dan is uw hele functie is O(log n). Het is vrij gebruikelijk dat elke stap in plaats daarvan lineaire tijd vereist op de invoer; dit zal neerkomen op een totale tijdscomplexiteit van O(n log n).

De looptijdcomplexiteit van binair zoeken is een voorbeeld van O(log n). Dit komt omdat je bij binair zoeken altijd de helft van je invoer negeert in elke latere stap door de array in tweeën te delen en je bij elke stap slechts op de helft te concentreren. Elke stap is een constante tijd, omdat u bij binair zoeken slechts één element met uw sleutel hoeft te vergelijken om erachter te komen wat u vervolgens moet doen, ongeacht hoe groot de array die u overweegt op enig moment is. U voert dus ongeveer log(n)/log(2) stappen uit.

De looptijdcomplexiteit van merge sort is een voorbeeld van O(n log n). Dit komt omdat je de array bij elke stap in tweeën deelt, wat resulteert in een totaal van ongeveer log(n)/log(2) stappen. In elke stap moet u echter samenvoegbewerkingen uitvoeren op alle elementen (of het nu één samenvoegbewerking is op twee sublijsten van n/2 elementen, of twee samenvoegbewerkingen op vier sublijsten van n/4 elementen, is niet relevant omdat het de doe dit voor n elementen in elke stap). De totale complexiteit is dus O(n log n).

*Onthoud dat de big-O-notatie, per definitie, constanten er niet toe doen . Ook door de wijziging van de basisregel voor logaritmen, is het enige verschil tussen logaritmen van verschillende basen een constante factor.

---

Antwoord 19

Simpel gezegd: bij elke stap van je algoritme kun je het werk halveren. (Asymptotisch gelijk aan derde, vierde, …)

---

Antwoord 20

Als je een logaritmische functie uitzet op een grafische rekenmachine of iets dergelijks, zul je zien dat deze heel langzaam stijgt — zelfs langzamer dan een lineaire functie.

Dit is de reden waarom algoritmen met een logaritmische tijdcomplexiteit zeer gewild zijn: zelfs voor echt grote n (laten we zeggen n = 10^8, bijvoorbeeld), presteren ze meer dan acceptabel.

---

Antwoord 21

Maar wat is O(log n) precies

Wat het precies betekent is “zoals n neigt naar infinity, de time neigt naar a*log(n) waarbij a een constante schaalfactor is”.

Of eigenlijk betekent het dat niet helemaal; waarschijnlijker betekent het zoiets als “time gedeeld door a*log(n) neigt naar 1“.

‘Nigt naar’ heeft de gebruikelijke wiskundige betekenis van ‘analyse’: bijvoorbeeld dat ‘als je een willekeurig kleine constante k kiest, kan een corresponderende waarde X vinden zodat ((time/(a*log(n))) - 1) kleiner is dan k voor alle waarden van n groter dan X.”

---

In lekentermen betekent dit dat de vergelijking voor tijd enkele andere componenten kan hebben: b.v. het kan een constante opstarttijd hebben; maar deze andere componenten verbleken in de richting van onbeduidendheid voor grote waarden van n, en de a*log(n) is de overheersende term voor grote n.

Merk op dat als de vergelijking bijvoorbeeld was …

time(n) = a + blog(n) + cn + dnn

… dan zou dit O(n kwadraat) zijn omdat, ongeacht de waarden van de constanten a, b, c en niet-nul d, de d*n*n term zou altijd domineren over de andere voor elke voldoende grote waarde van n.

Dat is wat bit O-notatie betekent: het betekent “wat is de volgorde van de dominante term voor een voldoende grote n”.

---

Antwoord 22

Ik kan er nog iets interessants aan toevoegen, dat ik lang geleden in een boek van Kormen e.d. heb gelezen. Stel je nu een probleem voor, waarbij we een oplossing moeten vinden in een probleemruimte. Deze probleemruimte moet eindig zijn.

Als je nu kunt bewijzen dat je bij elke iteratie van je algoritme een fractie van deze ruimte afsnijdt, dat is niet minder dan een limiet, dan betekent dit dat je algoritme in O(logN) tijd draait.

p>

Ik moet erop wijzen dat we het hier hebben over een relatieve breuklimiet, niet de absolute. De binaire zoekopdracht is een klassiek voorbeeld. Bij elke stap gooien we 1/2 van de probleemruimte weg. Maar binair zoeken is niet het enige voorbeeld. Stel dat je op de een of andere manier hebt bewezen dat je bij elke stap minstens 1/128 probleemruimte weggooit. Dat betekent dat uw programma nog steeds op O(logN)-tijd draait, hoewel aanzienlijk langzamer dan de binaire zoekopdracht. Dit is een zeer goede hint bij het analyseren van recursieve algoritmen. Vaak kan worden bewezen dat bij elke stap de recursie niet meerdere varianten zal gebruiken, en dit leidt tot de afsnijding van een fractie in de probleemruimte.

---

Antwoord 23

Elke keer dat we een algoritme of code schrijven, proberen we de asymptotische complexiteit ervan te analyseren.
Het is anders dan zijn tijdscomplexiteit.

Asymptotische complexiteit is het gedrag van de uitvoeringstijd van een algoritme, terwijl de tijdcomplexiteit de werkelijke uitvoeringstijd is. Maar sommige mensen gebruiken deze termen door elkaar.

Omdat de complexiteit van tijd afhankelijk is van verschillende parameters, namelijk
1. Fysiek systeem
2. Programmeertaal
3. coderingsstijl
4. En nog veel meer ……

De werkelijke uitvoeringstijd is geen goede maatstaf voor analyse.

In plaats daarvan nemen we de invoergrootte als parameter, want wat de code ook is, de invoer is hetzelfde.
Dus de uitvoeringstijd is een functie van de invoergrootte.

Hier volgt een voorbeeld van een lineair tijdalgoritme

Lineair zoeken

Gegeven n invoerelementen, om een ​​element in de array te zoeken, hebt u maximaal ‘n’ vergelijkingen nodig. Met andere woorden, het maakt niet uit welke programmeertaal je gebruikt, welke coderingsstijl je voorkeur heeft, op welk systeem je het uitvoert. In het ergste geval zijn er slechts n vergelijkingen nodig. De uitvoeringstijd is lineair evenredig met de invoergrootte.

En het is niet alleen zoeken, wat het werk ook is (verhogen, vergelijken of een bewerking), het is een functie van de invoergrootte.

Dus als je zegt dat een algoritme O(log n) is
het betekent dat de uitvoeringstijd log maal de invoergrootte n is.

Naarmate de invoer groter wordt, neemt het uitgevoerde werk (hier de uitvoeringstijd) toe. (Vandaar evenredigheid)

      n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work

Zie naarmate de invoer groter wordt, wordt het uitgevoerde werk groter en is het onafhankelijk van welke machine dan ook.
En als je de waarde van werkeenheden probeert te achterhalen
Het is eigenlijk afhankelijk van de hierboven gespecificeerde parameters. Het zal veranderen afhankelijk van de systemen en zo.

---

Antwoord 24

Ik kan een voorbeeld geven voor een for-lus en misschien, als ik het concept eenmaal heb begrepen, is het misschien eenvoudiger te begrijpen in verschillende contexten.

Dat betekent dat in de lus de stap exponentieel groeit. bijv.

for (i=1; i<=n; i=i*2) {;}

De complexiteit in O-notatie van dit programma is O(log(n)). Laten we proberen er met de hand doorheen te lopen (n is ergens tussen 512 en 1023 (exclusief 1024):

step: 1   2   3   4   5    6    7    8     9     10
   i: 1   2   4   8   16   32   64   128   256   512

Hoewel n ergens tussen 512 en 1023 ligt, vinden er slechts 10 iteraties plaats. Dit komt omdat de stap in de lus exponentieel groeit en er dus slechts 10 iteraties nodig zijn om de beëindiging te bereiken.

De logaritme van x (naar het grondtal van a) is de omgekeerde functie van a^x.

Het is alsof je zegt dat logaritme het omgekeerde is van exponentieel.

Probeer het nu zo te zien, als exponentieel erg snel groeit, dan groeit logaritme (omgekeerd) erg langzaam.

Het verschil tussen O(n) en O(log(n)) is enorm, vergelijkbaar met het verschil tussen O(n) en O(a^n) (a is een constante).

---

Antwoord 25

In feite, als je een lijst met n elementen hebt en een binaire boom van die lijst maakt (zoals in het verdeel en heers-algoritme), blijf je delen door 2 totdat je lijsten van grootte 1 (de bladeren) bereikt.

Bij de eerste stap deel je door 2. Je hebt dan 2 lijsten (2^1), je deelt ze elk door 2, dus je hebt 4 lijsten (2^2), je deelt opnieuw, je hebt 8 lijsten ( 2^3) enzovoort totdat uw lijstgrootte 1 is

Dat geeft je de vergelijking:

n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps

(u neemt de lg van elke kant, lg is de logbasis 2)

---

Antwoord 26

Het volledige binaire voorbeeld is O(ln n) omdat de zoekopdracht er als volgt uitziet:

1 2 3 4 5 6 7 8 9 10 11 12

Zoeken naar 4 levert 3 treffers op: 6, 3 dan 4. En log2 12 = 3, wat een goede schatting is van het aantal treffers waar nodig.

---

Antwoord 27

log x to base b = y is het omgekeerde van b^y = x

Als je een M-ary boom met diepte d en grootte n hebt, dan:

• de hele boom doorkruisen ~ O(M^d) = O(n)

• Een enkel pad in de boom lopen ~ O(d) = O(log n naar basis M)

---

Antwoord 28

In de informatietechnologie betekent dit dat:

  f(n)=O(g(n)) If there is suitable constant C and N0 independent on N, 
  such that
  for all N>N0  "C*g(n) > f(n) > 0" is true.

Het lijkt erop dat deze notatie grotendeels uit de wiskunde is overgenomen.

In dit artikel staat een citaat:
D.E. Knuth, “GROTE OMICRON EN GROTE OMEGA EN GROTE THETA”, 1976:

Op basis van de problemen die hier worden besproken, stel ik voor dat leden van
SIGACT, en redacteuren van informatica- en wiskundetijdschriften,
gebruik notaties zoals hierboven gedefinieerd, tenzij een beter alternatief kan zijn
redelijk snel gevonden.

Vandaag is het 2016, maar we gebruiken het nog steeds.

---

In wiskundige analyse betekent dit dat:

  lim (f(n)/g(n))=Constant; where n goes to +infinity

Maar zelfs in wiskundige analyse werd dit symbool soms gebruikt in de betekenis van “C*g(n) > f(n) > 0”.

Zoals ik weet van de universiteit is het symbool geïntroduceerd door de Duitse wiskundige Landau (1877-1938)

---

Antwoord 29

Als u op zoek bent naar een op intuïtie gebaseerd antwoord, wil ik graag twee interpretaties voor u opstellen.

1. Stel je een zeer hoge heuvel voor met ook een zeer brede basis. Om de top van de heuvel te bereiken zijn er twee manieren: de ene is een speciaal pad dat spiraalvormig rond de heuvel loopt en de top bereikt, de andere: een klein terras als uitsnijdingen die zijn uitgesneden om een ​​trap te vormen. Als nu de eerste manier is om in lineaire tijd O(n) te bereiken, is de tweede O(log n).

2. Stel je een algoritme voor dat een geheel getal, n als invoer accepteert en in de tijd proportioneel aan n voltooit, dan is het O(n) of theta(n ) maar als het in de tijd loopt in verhouding tot het number of digits or the number of bits in the binary representation on number, dan werkt het algoritme in O(log n) of theta(log n) tijd.

---

Antwoord 30

O(logn) is een van de polynomiale tijdcomplexiteit om de runtime-prestaties van elke code te meten.

Ik hoop dat je al hebt gehoord van het binaire zoekalgoritme.

Laten we aannemen dat je een element moet vinden in de array met grootte N.

In principe is de uitvoering van de code als volgt:
N
N/2
N/4
N/8….enz.

Als je al het werk optelt dat op elk niveau is gedaan, krijg je n(1+1/2+1/4….) en dat is gelijk aan O(logn)