Waarom is de constante altijd gedaald van BIG O-analyse?

Ik probeer een bepaald aspect van BIG O-analyse te begrijpen in het kader van het uitvoeren van programma’s op een pc.

Stel dat ik een algoritme heb met een uitvoering van O (N + 2). Hier als n echt groot wordt, wordt de 2 onbeduidend. In dit geval is het volkomen duidelijk dat de echte prestatie O (n) is.

Zeg echter een ander algoritme een gemiddelde prestaties van O (N ^{2 / 2) heeft. Het boek waar ik dit voorbeeld zag, zegt dat de echte prestatie O (N 2 ) is. Ik weet niet zeker of ik begrijp, ik bedoel, de 2 in dit geval lijkt niet volledig onbeduidend niet. Dus ik was op zoek naar een mooie duidelijke verklaring uit het boek. Het boek legt het op deze manier uit:}

“Overweeg echter wat de 1/2 betekent. De werkelijke tijd om elke waarde te controleren
is sterk afhankelijk van de machine-instructie die de code
Vertaalt naar en vervolgens op de snelheid waarmee de CPU de instructies kan uitvoeren. Daarom betekent de 1/2 niet erg veel. “

en mijn reactie is … huh? Ik heb letterlijk geen idee wat dat zegt of nauwkeuriger wat die verklaring heeft met hun conclusie. Kan iemand het alsjeblieft voor me uitspellen.

Bedankt voor alle hulp.

Antwoord 1, Autoriteit 100%

Er is een onderscheid tussen “zijn deze constanten betekenisvol of relevant?” en “doet Big-O-notatie om hen?” Het antwoord op die tweede vraag is “Nee”, terwijl het antwoord op die eerste vraag “Absoluut!”

is

BIG-O NOTATIE geeft niet om constanten omdat BIG-O-notatie alleen de langetermijngroei van functies beschrijft, in plaats van hun absolute magnitudes. Het vermenigvuldigen van een functie door een constante beïnvloedt alleen de groeipercentage door een constant bedrag, dus lineaire functies groeien nog steeds lineair, logaritmische functies groeien nog steeds logaritmisch, exponentiële functies groeien nog steeds exponentieel, enz. Omdat deze categorieën niet door constanten worden beïnvloed, is het niet dat we de constanten laten vallen.

Dat gezegd hebbende, die constanten zijn absoluut significant! Een functie waarvan de runtime 10 ^{100 N is, is manier langzamer dan een functie waarvan de runtime slechts n is. Een functie waarvan de runtime is N 2 / 2 zal sneller zijn dan een functie waarvan de runtime slechts N 2 is. Het feit dat de eerste twee functies zowel O (N) en de tweede twee zijn o (n 2 ) verandert niet dat ze niet in dezelfde hoeveelheid tijd draaien, sindsdien Dat is niet waar BIG-O-notatie is ontworpen. O Notatie is goed voor het bepalen of op de lange termijn één functie groter is dan een ander. Hoewel 10 100 N een kolossaal enorme waarde is voor elke N & GT; 0, Die functie is O (n) en dus voor groot genoeg is het uiteindelijk de functie waarvan de runtime n 2 / 2 is, omdat die functie O (N 2 is ).}

Samenvatting – Omdat BIG-O alleen gesprekken over relatieve klassen van groeipercentages, negeert het de constante factor. Die constanten zijn echter absoluut significant; Ze zijn gewoon niet relevant voor een asymptotische analyse.

Ik hoop dat dit helpt!

Antwoord 2, Autoriteit 4%

BIG-O NOTATIE beschrijft alleen de groei van algoritmen in termen van wiskundige functie, in plaats van de werkelijke looptijd van algoritmen op een computer.

Wiskundig, laat f (x) en g (x) positief voor x voldoende groot.
We zeggen dat f (x) en g (x) met hetzelfde tarief groeien als x neigt tot oneindig, als

Laat F (x) = x ^ 2 en g (x) = x ^ 2/2, dan lim (x- & gt; infinity) f (x) / g (x) = 2. SO x ^ 2 en x ^ 2/2 hebben beide dezelfde groeisnelheid. Dus we kunnen o (x ^ 2/2) = O (x ^ 2) zeggen.

Zoals templatetypedef zei, verborgen constanten in asymptotische notaties zijn absoluut significant.As een voorbeeld: Marge sorteert in O (NLOGN) worst-case tijd en invoeging sorteert in O (N ^ 2) worst case tijd. Verborgen constante factoren in Insertion Sorteer is kleiner dan die van Marge Sorteer, in de praktijk Insertion Sort kan sneller zijn dan Marge Sorteer voor kleine probleemmaten op veel machines.

Antwoord 3, Autoriteit 4%

Big O-notatie wordt meestal gebruikt om de looptijd van een algoritme te beschrijven. In deze context zou ik willen stellen dat specifieke constante waarden in wezen zinloos zijn. Stel je het volgende gesprek voor:

Alice: Wat is de looptijd van uw algoritme?

Bob: 7n²

Alice: Wat bedoel je met 7n²?

• Wat zijn de eenheden? Microseconden? Milliseconden? Nanoseconden?
• Op welke CPU gebruik je het? Intel i9-9900K? Qualcomm Snapdragon 845? (Of gebruik je een GPU, een FPGA of andere hardware?)
• Welk type RAM gebruik je?
• In welke programmeertaal heb je het algoritme geïmplementeerd? Wat is de broncode?
• Welke compiler/VM gebruikt u? Welke vlaggen geef je door aan de compiler / VM?
• Wat is het besturingssysteem?
• enz.

Zoals je kunt zien, is elke poging om een ​​specifieke constante waarde aan te geven inherent problematisch. Maar zodra we constante factoren opzij zetten, kunnen we de looptijd van een algoritme duidelijk beschrijven. Big O-notatie geeft ons een robuuste en bruikbare beschrijving van hoe lang een algoritme duurt, terwijl we abstraheren van de technische kenmerken van de implementatie en uitvoering ervan.

Het is nu mogelijk om de constante factor te specificeren bij het beschrijven van het aantal bewerkingen (geschikt gedefinieerd) of CPU-instructies die een algoritme uitvoert, het aantal vergelijkingen dat een sorteeralgoritme uitvoert, enzovoort. Maar meestal zijn we echt geïnteresseerd in de looptijd.

Niets van dit alles is bedoeld om te suggereren dat de werkelijke prestatiekenmerken van een algoritme onbelangrijk zijn. Als u bijvoorbeeld een algoritme voor matrixvermenigvuldiging nodig heeft, is het Coppersmith-Winograd-algoritme niet aan te raden. Het is waar dat dit algoritme O(n^2.376) tijd kost, terwijl het Strassen-algoritme, zijn sterkste concurrent, O(n^2.808) tijd kost. Volgens Wikipedia is Coppersmith-Winograd in de praktijk echter traag, en “het biedt alleen een voordeel voor matrices die zo groot zijn dat ze niet door moderne hardware kunnen worden verwerkt.” Dit wordt meestal verklaard door te zeggen dat de constante factor voor Kopersmid-Winograd erg groot is. Maar nogmaals, als we het hebben over de looptijd van Coppersmith-Winograd, heeft het geen zin om een ​​specifiek getal te geven voor de constante factor.

Ondanks de beperkingen is de grote O-notatie een redelijk goede maatstaf voor de looptijd. En in veel gevallen vertelt het ons welke algoritmen het snelst zijn voor voldoende grote invoergroottes, voordat we zelfs maar een enkele regel code schrijven.

Antwoord 4, autoriteit 3%

Je hebt helemaal gelijk dat constanten ertoe doen. Bij het vergelijken van veel verschillende algoritmen voor hetzelfde probleem, geven de O-getallen zonder constanten u een overzicht van hoe ze zich tot elkaar verhouden. Als je dan twee algoritmen in dezelfde O-klasse hebt, zou je ze vergelijken met de betrokken constanten.

Maar zelfs voor verschillende O-klassen zijn de constanten belangrijk. Bijvoorbeeld, voor multidigit of big integer-vermenigvuldiging is het naïeve algoritme O(n^2), Karatsuba is O(n^log_2(3)), Toom-Cook O(n^log_3(5)) en Schönhage-Strassen O (n*log(n)*log(log(n))). Elk van de snellere algoritmen heeft echter een steeds grotere overhead die wordt weerspiegeld in grote constanten. Dus om geschatte kruispunten te krijgen, heb je geldige schattingen van die constanten nodig. Zo krijgt men als SWAG dat tot n=16 de naïeve vermenigvuldiging het snelst is, tot n=50 Karatsuba en de oversteek van Toom-Cook naar Schönhage-Strassen voor n=200.

In werkelijkheid zijn de overgangspunten niet alleen afhankelijk van de constanten, maar ook van processorcaching en andere hardwaregerelateerde problemen.

Antwoord 5, autoriteit 3%

Grote O zonder constante is genoeg voor algoritme-analyse.

Ten eerste hangt de werkelijke tijd niet alleen af ​​van het aantal instructies, maar ook van de tijd voor elke instructie, die nauw verbonden is met het platform waarop de code wordt uitgevoerd. Het is meer dan theorie-analyse. Dus de constante is in de meeste gevallen niet nodig.

Ten tweede wordt Big O voornamelijk gebruikt om te meten hoe de runtime zal toenemen naarmate het probleem groter wordt of hoe de runtime afneemt naarmate de prestaties van de hardware verbeteren.

Ten derde, voor situaties van optimalisatie van hoge prestaties, wordt ook rekening gehouden met constante.

Antwoord 6

De tijd die tegenwoordig nodig is om een ​​bepaalde taak op computers uit te voeren, vereist niet veel tijd, tenzij de ingevoerde waarde erg groot is.

Stel dat we 2 matrices van grootte 10*10 willen vermenigvuldigen, dan hebben we geen probleem tenzijwe deze bewerking meerdere kerenwillen doen en dan de rol van asymptotische notaties overheersenen wanneer de waarde van n erg groot wordt, maken de constanten niet echt een verschil voor het antwoord en zijn ze bijna te verwaarlozen, dus we hebben de neiging ze te laten tijdens het berekenen de complexiteit.

Antwoord 7

Tijdcomplexiteit voor O(n+n)wordt gereduceerd tot O(2n). Nu is 2een constante. De tijdscomplexiteit hangt dus in wezen af ​​van n.
Vandaar dat de tijdscomplexiteit van O(2n)gelijk is aan O(n).
Ook als er zoiets is O(2n + 3), zal het nog steeds O(n)zijn, aangezien de tijd in wezen afhangt van de grootte van n.
Stel nu dat er een code is die O(n^2 + n)is, dan zal het O(n^2)zijn, want wanneer de waarde van n het effect van n wordt minder significant in vergelijking met het effect van n^2.
Bijv.:

n = 2  => 4 + 2 = 6
n = 100 => 10000 + 100 => 10100
n = 10000 => 100000000 + 10000 => 100010000 

Zoals je kunt zien, is het effect van de tweede uitdrukking een kleiner effect omdat de waarde van nblijft toenemen. Vandaar dat de tijdcomplexiteit evalueert tot O(n^2).