Kompleksitas waktu 2 ^ sqrt (n)

Saya memecahkan pertanyaan algoritma dan analisis saya adalah bahwa itu akan berjalan pada O (2 ^ sqrt (n)). Seberapa besar itu? Apakah ini sama dengan O (2 ^ n)? Apakah ini masih waktu non-polinomial?

Ini pertanyaan yang menarik. Untungnya, begitu Anda tahu bagaimana menyelesaikannya, itu tidak terlalu sulit.

Untuk fungsi f : N → R ⁺ dan g : N → R ⁺ , kita memiliki f ∈ O ( g ) jika dan hanya jika lim sup _{n → ∞} f ( n ) / g ( n ) ∈ R .

Fungsi f : N → R ⁺ memiliki paling banyak pertumbuhan polinomial jika dan hanya jika ada konstanta k ∈ N sedemikian rupa sehingga f ∈ O ( n ↦ n ^k ). Mari kita bekerja keluar ini untuk sewenang-wenang tetapi tetap k ∈ N .

lim sup _{n → ∞} 2 ^{( n 1/2 )} / n ^k =
lim _{n → ∞} 2 ^{( n 1/2 )} / n ^k =
lim _{n → ∞} e ^{log (2) n 1/2} / e ^{log ( n ) k} =
lim _{n → ∞} e ^{log (2) n 1/2 - log ( n ) k} = ∞ ∉ R

Kesetaraan pertama benar karena keduanya, nominator dan denominator, adalah fungsi stabil yang tumbuh secara monoton. Kesetaraan kedua menggunakan identitas x ^y = e ^{log ( x ) y} . Batas tidak terbatas karena eksponen dalam ekspresi akhir tidak dibatasi di atas. Tanpa memberikan bukti formal, dapat diasumsikan diketahui bahwa n ^1/2 mendominasi log ( n ) asimptotik. Oleh karena itu, fungsi yang dimaksud melebihi pertumbuhan polinomial.

Namun, pertumbuhannya benar-benar kurang dari eksponensial, di mana eksponensial didefinisikan (oleh saya, untuk tujuan ini) sebagai O ( n ↦ 2 ^{c n} ) untuk c > 0. Menunjukkan ini bahkan lebih lurus ke depan.

lim sup _{n → ∞} 2 ^{c n} / 2 ^{( n 1/2 )} = lim _{n → ∞} 2 ^{c n - n 1/2} = ∞ ∉ R

untuk c tetap 0.> Oleh karena itu, kompleksitas fungsi berada di suatu tempat di antara polinomial dan eksponensial.

Seberapa besar itu? Nah, O (2 ^ sqrt (n)) persis seberapa besar :-(

Untuk mendapatkan gambaran tentang apa artinya, bayangkan algoritma Anda bukan hanya O (2 ^ sqrt (n)), tetapi sebenarnya dibutuhkan 2 ^ sqrt (n) nanodetik di komputer Anda:

n = 100: 2 ^ 10 = 1024 nanodetik. Tidak ada waktu sama sekali. n = 1000: 2 ^ 31.xxx = 2 miliar nanodetik. Dua detik, itu terlihat. n = 10.000: 2 ^ 100 ≈ 10 ^ 30 nanodetik = 10 ^ 21 detik = 30 triliun tahun.

Ini jauh lebih baik daripada 2 ^ nanodetik, di mana n = 100 akan memakan waktu 30 triliun tahun, tetapi ukuran masalah yang masih bisa Anda pecahkan sangat terbatas. Jika Anda menganggap masalah "dapat dipecahkan" jika komputer Anda dapat menyelesaikannya dalam satu minggu, itu sekitar 6 x 10 ^ 14 nanodetik, itu sekitar n = 2.400. Di sisi lain, hingga n = 400 dapat diselesaikan dalam milidetik.

(Dalam praktiknya, untuk n = 10.000 baik O (2 ^ sqrt (n)) dan O (2 ^ n) mengambil waktu yang persis sama: Terlalu lama untuk menunggu.)

Itu melebihi polinomial apa pun. Ambil algoritma lain yang membutuhkan n ^ 1000 detik. Yang praktis tidak dapat dipecahkan untuk n = 2. Algoritma ini membutuhkan waktu lebih lama hingga n adalah sekitar 885 juta. Tapi sungguh, siapa yang peduli? Pada saat itu, jumlah tahun yang dibutuhkan kedua algoritma adalah angka 9.000 digit.