Apakah 2 ^ n dan n * 2 ^ n dalam kompleksitas waktu yang sama?

178

Sumber daya yang saya temukan pada kompleksitas waktu tidak jelas kapan boleh mengabaikan istilah dalam persamaan kompleksitas waktu, khususnya dengan contoh non-polinomial.

Jelas bagi saya bahwa diberi sesuatu dari bentuk n 2 + n + 1, dua istilah terakhir tidak signifikan.

Secara khusus, diberikan dua kategorisasi, 2 n , dan n * (2 n ), apakah urutan kedua sama dengan yang pertama? Apakah n perkalian tambahan itu penting? Biasanya sumber daya hanya mengatakan xn berada dalam eksponensial dan tumbuh jauh lebih cepat ... kemudian beralih.

Saya bisa mengerti mengapa itu tidak akan karena 2 n akan jauh melebihi n, tetapi karena mereka tidak ditambahkan bersama-sama, akan sangat penting ketika membandingkan dua persamaan, pada kenyataannya perbedaan di antara mereka akan selalu menjadi faktor n, yang tampaknya penting untuk sedikitnya.

algorithm big-o complexity-theory time-complexity matty-d
sumber
8
Menurut pendapat saya, mengingat bahwa NLogN dianggap lebih lambat dari N, tetapi kebanyakan orang tidak terlalu peduli dengan seberapa banyak, aman untuk mengatakan N2 ^ N hanya lebih lambat dari 2 ^ N, tetapi tidak "cukup lambat" untuk orang untuk peduli ..
Jack
@tobias_k, saya mengerti hal ini, tetapi perhatikan contoh O (n!). Apakah istilah tambahan benar-benar berbeda? O (n!) Adalah untuk O (n * n!) Karena O (n!) Adalah untuk O ((n + 1)!) Alias ​​grafik yang sama hanya bergeser. Tetapi pertumbuhannya sama ... Dalam hal ini walaupun satu sangat besar, apakah pertumbuhannya berbeda? bukankah ini kompleksitas waktu peduli?
matty-d
3
@ JackWu tetapi kebanyakan orang tidak terlalu peduli dengan berapa banyak sampai Anda harus mengurutkan ratusan juta catatan dengan nlogn, bukan n :)
CB
4
Faktanya, n! = o((n+1)!)itu tumbuh sangat lambat tanpa gejala.
chepner
16
Perhatikan bahwa ini tidak ada hubungannya dengan teori kompleksitas, ini "hanya" tentang aimptotik. Juga, pertanyaan-pertanyaan semacam ini mungkin lebih baik di bidang Ilmu Komputer .
Raphael

Jawaban:

231

Anda harus pergi ke definisi formal dari O besar ( O) untuk menjawab pertanyaan ini.

Definisi adalah f(x)milik O(g(x))jika dan hanya jika ada batas yaitu tidak terbatas. Singkatnya ini berarti bahwa ada konstanta , sehingga nilai tidak pernah lebih besar dari .limsupx → ∞ (f(x)/g(x))Mf(x)/g(x)M

Dalam hal pertanyaan Anda, biarkan dan biarkan . Maka adalah yang masih akan tumbuh jauh. Karena itu bukan milik .f(n) = n ⋅ 2ng(n) = 2nf(n)/g(n)nf(n)O(g(n))

Ivaylo Strandjev
sumber
5
Untuk definisi yang sedikit lebih mudah dibaca, lihat di sini
Alden
3
Secara formal, Anda tidak dapat mengambil batas O(f(x)/g(x)); notifikasi big-O adalah singkatan untuk sekumpulan fungsi, bukan fungsi tunggal yang nilainya dapat Anda batasi. Namun, saya pikir itu benar bahwa Anda dapat menunjukkan bahwa f(x) = O(g(x))jika lim(x->infinity) f(x)/g(x)ada.
chepner
44
Batas tidak harus ada; rasio hanya harus dibatasi di atas oleh konstanta untuk x yang cukup besar. Sebagai contoh, 2 + sin (x) berada di O (1), tetapi (2 + sin (x)) / 1 tidak mendekati batas sebagai x-> infinity.
user2357112 mendukung Monica
2
Definisi akan benar dengan lim supalih - alih lim.
David Eisenstat
11
@IvayloStrandjev harap dicatat bahwa uraian singkat Anda salah. Ini harus benar untuk yang cukup besar x, bukan untuk semua nilai x.
K.Steff
85

Cara cepat untuk melihat yang n⋅2ⁿlebih besar adalah dengan membuat perubahan variabel. Mari m = 2ⁿ. Kemudian n⋅2ⁿ = ( log₂m )⋅m(mengambil basis-2 logaritma di kedua sisi m = 2ⁿmemberi n = log₂m), dan Anda dapat dengan mudah menunjukkan bahwa m log₂mtumbuh lebih cepat daripada m.

chepner
sumber
3
Terima kasih! Ini jawaban terbaik menurut saya. Bukti berdasarkan definisi formal adalah benar, tetapi jika Anda memiliki batu sandungan untuk dilewati, analogi yang sangat nyaman dan akrab akan melakukan pekerjaan yang terbaik dan tercepat.
John P
1
Pertanyaan bodoh, apa itu lg? Logaritma di basis 2?
Pierre Arlaud
3
Ini adalah singkatan yang malas. Dalam ilmu komputer, itu cenderung berarti basis 2 karena sebagian besar hasil dari strategi membagi dan menaklukkan. Dalam notasi O-besar, ia dapat mewakili apa saja, karena logaritma basis-x dari suatu nomor berbeda dari logaritma basis-y hanya dengan faktor konstan, terlepas dari x dan y.
chepner
3
Saya harus mencatat dalam retrospeksi bahwa itu lgadalah notasi ISO untuk basis-10 logaritma, daripada penggunaan basis-agnostik yang paling umum digunakan ketika membahas waktu lari asimptotik. Lihat en.wikipedia.org/wiki/Logarithm#Particular_bases
chepner
Oke, tentu, tapi saya tidak mengerti mengapa lebih jelas bahwa m log m tumbuh lebih cepat daripada m, daripada n2 ^ n tumbuh lebih cepat dari 2 ^ n.
Djechlin
10

Saya setuju bahwa n⋅2ⁿtidak ada dalam O(2ⁿ), tetapi saya pikir itu harus lebih eksplisit karena batas penggunaan superior tidak selalu berlaku.

Dengan definisi formal Big-O: f(n)ada di O(g(n))jika ada konstanta c > 0dan n₀ ≥ 0sedemikian rupa sehingga untuk semua yang n ≥ n₀kita miliki f(n) ≤ c⋅g(n). Dapat dengan mudah ditunjukkan bahwa tidak ada konstanta untuk f(n) = n⋅2ⁿdan g(n) = 2ⁿ. Namun, dapat ditunjukkan bahwa g(n)ada di O(f(n)).

Dengan kata lain, n⋅2ⁿlebih rendah dibatasi oleh 2ⁿ. Ini intuitif. Meskipun keduanya eksponensial dan karenanya sama-sama tidak mungkin digunakan dalam sebagian besar situasi praktis, kita tidak dapat mengatakan bahwa keduanya memiliki urutan yang sama karena 2ⁿtentu tumbuh lebih lambat daripada n⋅2ⁿ.

zpr
sumber
f(n) = 2*2^nSaya pikir Anda maksud n*2^n?
tobias_k
4

Saya tidak berdebat dengan jawaban lain yang mengatakan bahwa n⋅2ⁿtumbuh lebih cepat daripada 2ⁿ. Tapi n⋅2ⁿtumbuh masih eksponensial.

Ketika kita berbicara tentang algoritma, kita sering mengatakan bahwa kompleksitas waktu tumbuh adalah eksponensial. Jadi, kami anggap 2ⁿ, 3ⁿ, eⁿ, 2.000001ⁿ, atau kami n⋅2ⁿmenjadi kelompok yang sama kompleksitas dengan eksponensial tumbuh.

Untuk memberikan sedikit pengertian matematis, kami menganggap fungsi f(x)untuk tumbuh (tidak lebih cepat dari) secara eksponensial jika ada yang konstan c > 1, yaitu .f(x) = O(cx)

Untuk n⋅2ⁿkonstanta cdapat angka lebih besar dari 2, mari kita ambil3 . Kemudian:

n⋅2ⁿ / 3ⁿ = n ⋅ (2/3)ⁿdan ini kurang dari 1apa pun n.

Jadi 2ⁿtumbuh lebih lambat daripada n⋅2ⁿ, yang terakhir tumbuh lebih lambat daripada 2.000001ⁿ. Namun ketiganya tumbuh secara eksponensial.

Andrey
sumber
Dalam contoh terakhir, n * 2 ^ n lebih besar dari 2.000001 ^ n hingga n = 34.726.000. Pada saat itu 2 ^ n adalah angka dengan lebih dari 10 juta digit, jadi tidak masalah ...
gnasher729
1
@ gnasher729 Ini hanya sebuah konstanta yang dapat kita hilangkan sebagai f (n) dan c * f (n) adalah kompleksitas yang sama dalam hal big-O. mis. 40'000'000 * 2.000001 ^ n lebih besar dari n * 2 ^ n segera. Tapi Anda benar, itu tidak terlalu penting, saya akan mengatakan itu tidak terlalu penting begitu kita mencapai pertumbuhan eksponensial (kecuali kita hanya mendapatkan nilai kecil n).
Andrey
2

Anda bertanya, "Apakah yang kedua dalam urutan yang sama dengan yang pertama? Apakah ada penambahan dan multiplikasi?" Ini adalah dua pertanyaan berbeda dengan dua jawaban berbeda.

n 2 ^ n tumbuh lebih cepat tanpa gejala dari 2 ^ n. Itu pertanyaan yang dijawab.

Tetapi Anda dapat bertanya "apakah algoritma A membutuhkan 2 ^ n nanodetik, dan algoritma B membutuhkan n 2 ^ n nanodetik, apa yang terbesar di mana saya dapat menemukan solusi dalam detik / menit / jam / hari / bulan / tahun? Dan jawabannya adalah n = 29/35/41/46/51/54 vs 25/30/36/40/45/49.Tidak banyak perbedaan dalam praktiknya.

Ukuran masalah terbesar yang dapat diselesaikan dalam waktu T adalah O (ln T) dalam kedua kasus.

gnasher729
sumber