Ar 2 ^ n ir n * 2 ^ n tuo pačiu metu yra sudėtingi?

Ištekliai, kuriuos atradau laiko sudėtingumu, nėra aiškūs, kai terminų sudėtingumo laiko lygtis gali būti ignoruojami, ypač su ne polinominiais pavyzdžiais.

Man aišku, kad, atsižvelgiant į kažką panašaus į n 2 + n + 1, paskutiniai du nariai nėra reikšmingi.

Visų pirma, atsižvelgiant į dvi kategorijas, 2 n ir n * (2 n ), yra antroji ta pačia tvarka kaip ir pirmoji? Ar yra papildomas dauginimas n? Paprastai ištekliai tiesiog sako, kad x n yra eksponentinis ir auga daug greičiau ... tada judėti toliau.

Galiu suprasti, kodėl tai neįvyks, nes 2 n yra gerokai aukštesnis už n, bet kadangi jie nėra kartu, tai labai svarbu lyginant dvi lygtis, iš tikrųjų skirtumas tarp jų visada bus n koeficientas, kuris, matyt, turi mažiausią vertę.

171
13 февр. matty-d yra nustatytas vasario 13 d 2014-02-13 23:32 '14, 23:32 2014-02-13 23:32
@ 5 atsakymai

Kad atsakytumėte į šį klausimą, turite pereiti prie oficialaus didelio O ( O ) apibrėžimo.

Apibrėžimas yra tas, kad f(x) priklauso O(g(x)) jei ir tik tuo atveju, jei yra ribinė riba limsup x → ∞ (f(x)/g(x)) , tai yra, ne begalinis. Trumpai tariant, tai reiškia, kad yra konstanta M , kad f(x)/g(x) vertė niekada neviršytų M

Jūsų klausimo atveju leiskite f(n) = n ⋅ 2 n ir g(n) = 2 n . Tada f(n)/g(n) yra n , kuris augs be galo. Todėl f(n) nepriklauso O(g(n)) .

219
13 февр. Ivaylo Strandjevo atsakymas vasario 13 d. 2014-02-13 23:44 '14, 23:44 2014-02-13 23:44

Greitas būdas pamatyti, kad n⋅2ⁿ daugiau, yra pakeisti kintamąjį. Leiskite m = 2ⁿ . Tada n⋅2ⁿ = ( log₂m )⋅m (atsižvelgiant į pagrindo-2 logaritmą iš abiejų pusių m = 2ⁿ suteikia n = log₂m ), ir jūs galite lengvai parodyti, kad m log₂m auga greičiau nei m .

80
13 февр. atsakymas suteiktas chepner 13 vasaris 2014-02-13 23:44 '14, 23:44 2014-02-13 23:44

Sutinku, kad n⋅2ⁿ nėra O(2ⁿ) , bet maniau, kad jis turėtų būti aiškesnis, nes ne visada pasiekiama puikios naudojimo riba.

Oficialiai apibrėžus, Big-O: f(n) yra O(g(n)) jei yra konstantos c > 0 ir n₀ ≥ 0 , kad visiems n ≥ n₀ mes turime f(n) ≤ c⋅g(n) . Tai lengva parodyti, kad f(n) = n⋅2ⁿ ir g(n) = 2ⁿ tokių konstantų nėra. Tačiau galima parodyti, kad g(n) yra O(f(n)) .

Kitaip tariant, žemiau n⋅2ⁿ yra tik 2ⁿ . Tai intuityvus. Nors jie abu yra eksponentiniai ir todėl mažai tikėtina, kad jie bus naudojami daugumoje praktinių sąlygų, negalime pasakyti, kad jie yra tos pačios eilės, nes 2ⁿ būtinai auga lėčiau nei n⋅2ⁿ .

10
14 февр. atsakymas pateikiamas zpr 14 feb . 2014-02-14 05:47 '14 at 5:47 2014-02-14 05:47

Aš nesutinku su kitais atsakymais, kuriuose teigiama, kad n⋅2ⁿ auga greičiau nei 2ⁿ . Bet n⋅2ⁿ vis dar auga tik eksponentiškai.

Kai kalbame apie algoritmus, dažnai sakome, kad laiko sudėtingumas auga eksponentiškai. Taigi, mes tikime, kad 2ⁿ , 3ⁿ , eⁿ , 2.000001ⁿ arba mūsų n⋅2ⁿ bus ta pati sudėtingumo grupė, turinti eksponentinį augimą.

Norėdami suteikti jai šiek tiek matematinės reikšmės, apsvarstykite f(x) funkciją eksponentiniam augimui (ne greičiau), jei yra konstanta c > 1 , kad f(x) = O(c x ) .

n⋅2ⁿ c konstanta c gali būti bet kuris skaičius, didesnis nei 2 ; Tada:

n⋅2ⁿ / 3ⁿ = n ⋅ (2/3)ⁿ , ir jis yra mažesnis nei 1 bet kuriam n .

Taigi, 2ⁿ auga lėčiau nei n⋅2ⁿ , pastarasis savo ruožtu auga lėčiau nei 2.000001ⁿ . Tačiau visi trys auga eksponentiškai.

4
21 февр. atsakymą pateikė Andrejus 21 vasaris. 2014-02-21 13:21 '14, 13:21 pm 2014-02-21 13:21

Jūs paklausėte: „Antrasis taip pat, kaip ir pirmasis?“. Ar papildomas dauginimasis yra svarbus? Tai du skirtingi klausimai, turintys du skirtingus atsakymus.

n 2 ^ n auga asimptotiškai greičiau nei 2 ^ n. Į šį klausimą atsakoma.

Bet jūs galite paklausti: „Jei A algoritmas trunka 2 ^ n nanosekundes, o B algoritmas n n ^ n nanosekundes, kas yra didžiausias n, kur galiu rasti sprendimą per sekundę / minutę / valandą / dieną / mėnesį / metus? Ir atsakymai: n = 29/35/41/46/51/54, palyginti su 25/30/36/40/45/49, praktikoje nėra daug skirtumų.

Didžiausios problemos, kurią galima išspręsti T laiku, dydis yra O (ln T) abiem atvejais.

2
18 марта '14 в 12:17 2014-03-18 12:17 atsakymą pateikė gnasher729 kovo 18 '14, 12:17 2014-03-18 12:17