Bronnen die ik heb gevonden over tijdcomplexiteit, is onduidelijk over wanneer het oké is om termen in een tijdcomplexiteitsvergelijking te negeren, met name bij niet-polynomiale voorbeelden.
Het is mij duidelijk dat gegeven iets van de vorm n2+ n + 1, de laatste twee termen onbeduidend zijn.
In het bijzonder, gezien twee categorisaties, 2nen n*(2n), is de tweede in dezelfde volgorde als de eerste? Is de extra n-vermenigvuldiging daar van belang? Gewoonlijk zeggen bronnen gewoon dat xnexponentieel is en veel sneller groeit… ga dan verder.
Ik kan begrijpen waarom het niet zou zijn, aangezien 2nveel groter zal zijn dan n, maar omdat ze niet bij elkaar worden opgeteld, zou het enorm veel uitmaken bij het vergelijken van de twee vergelijkingen, in feite het verschil tussen hen zal altijd een factor n zijn, wat op zijn zachtst gezegd belangrijk lijkt.
Antwoord 1, autoriteit 100%
Je moet naar de formele definitie van de grote O (O) gaan om deze vraag te beantwoorden.
De definitie is dat f(x)behoort tot O(g(x))als en alleen als de limiet limsupx → ∞(f(x)/g(x))bestaat dwz is niet oneindig. In het kort betekent dit dat er een constante mbestaat, zodanig dat de waarde van f(x)/g(x)nooit groter is dan m.
Laat in het geval van uw vraag f(n) = n ⋅ 2nen laat g(n) = 2n. Dan is f(n)/g(n)ndie nog steeds oneindig zal groeien. Daarom hoort f(n)niet bij O(g(n)).
Antwoord 2, autoriteit 37%
Een snelle manier om te zien dat n⋅2ⁿgroter is, is door een variabele te wijzigen. Laat m = 2ⁿ. Dan n⋅2ⁿ = ( log₂m )⋅m(het nemen van de logaritme met grondtal-2 aan beide zijden van m = 2ⁿgeeft n = log₂m) , en je kunt gemakkelijk laten zien dat m log₂msneller groeit dan m.
Antwoord 3, autoriteit 4%
Ik ben het ermee eens dat n⋅2ⁿniet in O(2ⁿ)staat, maar ik vond dat het explicieter moest zijn, aangezien de limiet voor superieur gebruik niet altijd geldt.
Volgens de formele definitie van Big-O: f(n)staat in O(g(n))als er constanten bestaan c > 0en n₀ ≥ 0zodat voor alle n ≥ n₀we f(n) ≤ c⋅g(n)hebben . Het kan gemakkelijk worden aangetoond dat dergelijke constanten niet bestaan voor f(n) = n⋅2ⁿen g(n) = 2ⁿ. Het kan echter worden aangetoond dat g(n)in O(f(n))staat.
Met andere woorden, n⋅2ⁿwordt lager begrensd door 2ⁿ. Dit is intuïtief. Hoewel ze allebei exponentieel zijn en het dus even onwaarschijnlijk is dat ze in de meeste praktische omstandigheden worden gebruikt, kunnen we niet zeggen dat ze van dezelfde orde zijn, omdat 2ⁿnoodzakelijkerwijs langzamer groeit dan n⋅2ⁿ.
Antwoord 4, autoriteit 2%
Ik maak geen ruzie met andere antwoorden die zeggen dat n⋅2ⁿsneller groeit dan 2ⁿ. Maar n⋅2ⁿgroeit nog steeds exponentieel.
Als we het over algoritmen hebben, zeggen we vaak dat de complexiteit van de tijd exponentieel toeneemt.
We beschouwen dus als 2ⁿ, 3ⁿ, eⁿ, 2.000001ⁿ, of onze n⋅2ⁿdezelfde groep van complexiteit zijn met exponentiële groei.
Om het een beetje wiskundige betekenis te geven, beschouwen we een functie f(x)om (niet sneller dan) exponentieel te groeien als er zo’n constante c > 1, dat f(x) = O(cx).
Voor n⋅2ⁿkan de constante celk getal groter dan 2zijn, laten we 3nemen. Dan:
n⋅2ⁿ / 3ⁿ = n ⋅ (2/3)ⁿen dit is minder dan 1voor elke n.
Dus 2ⁿgroeit langzamer dan n⋅2ⁿ, de laatste groeit op zijn beurt langzamer dan 2.000001ⁿ. Maar ze groeien alle drie exponentieel.
Antwoord 5
Je vroeg “is de tweede in dezelfde volgorde als de eerste? Maakt de extra n-vermenigvuldiging daar uit?” Dit zijn twee verschillende vragen met twee verschillende antwoorden.
n 2^n groeit asymptotisch sneller dan 2^n. Dat is die vraag beantwoord.
Maar je zou kunnen vragen “als algoritme A 2^n nanoseconden kost, en algoritme B n 2^n nanoseconden, wat is dan de grootste n waar ik een oplossing kan vinden in een seconde / minuut / uur / dag / maand / jaar? En de antwoorden zijn n = 29/35/41/46/51/54 vs. 25/30/36/40/45/49. In de praktijk niet veel verschil.
De grootte van het grootste probleem dat in tijd T kan worden opgelost, is in beide gevallen O (ln T).
Antwoord 6
Heel eenvoudig antwoord is ‘NEE’
zie 2^nen n.2^n
zoals gezien n.2^n > 2^nvoor elke n>0
of je kunt het zelfs doen door log aan beide kanten toe te passen, dan krijg je
n.log(2) < n.log(2) + log(n)
vandaar beide soorten analyse, namelijk door
-
een nummer vervangen
-
log gebruiken
we zien dat n.2^ngroter is dan 2^nzoals zichtbaar is
dus als je een vergelijking krijgt zoals
O ( 2^n + n.2^n )die kan worden vervangen door O ( n.2^n)