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 m
bestaat, zodanig dat de waarde van f(x)/g(x)
nooit groter is dan m
.
Laat in het geval van uw vraag f(n) = n ⋅ 2n
en laat g(n) = 2n
. Dan is f(n)/g(n)
n
die 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₂m
sneller 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 > 0
en n₀ ≥ 0
zodat 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 c
elk getal groter dan 2
zijn, laten we 3
nemen. Dan:
n⋅2ⁿ / 3ⁿ = n ⋅ (2/3)ⁿ
en dit is minder dan 1
voor 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^n
en n.2^n
zoals gezien n.2^n > 2^n
voor 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^n
groter is dan 2^n
zoals zichtbaar is
dus als je een vergelijking krijgt zoals
O ( 2^n + n.2^n )
die kan worden vervangen door O ( n.2^n)