Apa pseudopolynomial waktu? Bagaimana itu berbeda dari jumlahnya banyak waktu? Beberapa algoritma yang berjalan di pseudopolynomial waktu telah runtimes suka O(nW) (untuk 0/1 Knapsack Problem) atau O(√n) (untuk trial division); mengapa doesn't yang dihitung sebagai polinomial waktu?
Untuk memahami perbedaan antara polinomial waktu dan pseudopolynomial waktu, kita perlu memulai dengan memformalkan apa "jumlahnya banyak waktu" berarti. Umum intuisi untuk jumlahnya banyak waktu "waktu O(nk) untuk beberapa k." misalnya, [selection sort][1] berjalan dalam waktu O(n2), yang jumlahnya banyak waktu, sedangkan brute-force memecahkan [SDT][2] membutuhkan waktu O(n · n!), yang isn't jumlahnya banyak waktu. Ini runtimes semua mengacu kepada beberapa variabel n yang melacak ukuran input. Misalnya, dalam selection sort, n mengacu pada jumlah elemen dalam array, sedangkan di SDT n mengacu pada jumlah node dalam grafik. Dalam rangka standarisasi definisi yang "n" benar-benar berarti dalam konteks ini, definisi formal dari kompleksitas waktu mendefinisikan "size" masalah sebagai berikut:
ukuran input terhadap suatu masalah adalah jumlah bit yang diperlukan untuk menulis bahwa input. Sebagai contoh, jika input untuk algoritma sorting adalah sebuah array dari 32-bit integer, maka ukuran input akan 32n, di mana n adalah jumlah data dalam array. Dalam sebuah graph dengan n simpul dan m tepi, masukan mungkin akan ditetapkan sebagai daftar dari semua node yang diikuti oleh daftar dari semua tepi, yang akan membutuhkan Ω(n + m) bit. Mengingat definisi ini, definisi formal dari waktu polinomial adalah sebagai berikut: algoritma berjalan dalam waktu polinomial jika runtime nya adalah O(xk) untuk beberapa konstanta k, dimana x menunjukkan jumlah bit dari masukan yang diberikan untuk algoritma. Ketika bekerja dengan algoritma bahwa proses grafik, daftar, pohon, dll., definisi ini lebih atau kurang setuju dengan definisi konvensional. Untuk contoh, misalkan anda memiliki sebuah algoritma sorting yang macam array dari 32-bit integer. Jika anda menggunakan sesuatu seperti semacam seleksi untuk melakukan hal ini, runtime, sebagai fungsi dari jumlah input elemen-elemen dalam array, akan menjadi O(n2). Tapi bagaimana n, jumlah elemen dalam array input, sesuai dengan jumlah bit dari input? Seperti disebutkan sebelumnya, jumlah bit input akan menjadi x = 32n. Oleh karena itu, jika kita mengekspresikan runtime dari algoritma dalam hal x daripada n, kita mendapatkan bahwa runtime adalah O(x2), dan algoritma berjalan dalam waktu polinomial. Demikian pula, misalkan anda melakukan [depth-first search][3] pada grafik, yang membutuhkan waktu O(m + n), di mana m adalah jumlah sisi di dalam graf, dan n adalah jumlah node. Bagaimana hal ini berhubungan dengan jumlah bit dari input yang diberikan? Nah, jika kita asumsikan bahwa input ditetapkan sebagai adjacency list (daftar semua node dan tepi), maka seperti yang disebutkan sebelumnya jumlah bit input akan menjadi x = Ω(m + n). Oleh karena itu, runtime akan menjadi O(x), sehingga algoritma ini berjalan dalam waktu polinomial. Hal-hal yang memecah, namun, ketika kita mulai berbicara tentang algoritma yang beroperasi pada angka-angka. Let's mempertimbangkan masalah pengujian apakah suatu bilangan prima atau tidak. Diberikan sejumlah n, anda dapat menguji jika n adalah bilangan prima menggunakan algoritma berikut:
function isPrime(n):
for i from 2 to n - 1:
if (n mod i) = 0, return false
return true
Jadi apa yang's waktu kompleksitas dari kode ini? Nah, itu inner loop berjalan O(n) kali dan setiap kali melakukan beberapa jumlah pekerjaan untuk menghitung n mod saya (sebagai benar-benar konservatif terikat atas, hal ini tentu dapat dilakukan dalam waktu O(n3)). Oleh karena itu, ini secara keseluruhan algoritma berjalan dalam waktu O(n4) dan mungkin jauh lebih cepat. Pada tahun 2004, tiga ilmuwan komputer menerbitkan sebuah makalah yang disebut [bilangan PRIMA adalah P][4] memberikan polynomial-time algorithm untuk menguji apakah nomor perdana. Itu dianggap sebagai landmark hasil. Jadi apa yang's the big deal? Don't kita sudah memiliki polynomial-time algorithm untuk ini, yaitu salah satu di atas? Sayangnya, kita don't. Ingat, definisi formal dari kompleksitas waktu pembicaraan tentang kompleksitas algoritma sebagai fungsi dari jumlah bit masukan. Algoritma kami berjalan dalam waktu O(n4), tapi apa yang sebagai fungsi dari jumlah input bit? Nah, menulis jumlah n membutuhkan waktu O(log n) bit. Oleh karena itu, jika kita membiarkan x sama dengan jumlah bit yang diperlukan untuk menulis input n, runtime dari algoritma ini sebenarnya adalah O(24x), yang adalah tidak polinomial dalam x. Ini adalah inti dari perbedaan antara waktu polinomial dan pseudopolynomial waktu. Di satu sisi, kita algoritma ini adalah O(n4), yang terlihat seperti sebuah polinomial, tetapi di sisi lain, di bawah definisi formal yang jumlahnya banyak waktu, it's tidak polynomial-time. Untuk mendapatkan intuisi mengapa algoritma ini isn't polynomial-time algorithm, berpikir tentang hal berikut. Misalkan saya ingin algoritma harus melakukan banyak pekerjaan. Jika saya menulis masukan seperti ini:
10001010101011 maka itu akan mengambil beberapa kasus terburuk jumlah waktu, katakan
T
, untuk menyelesaikan. Jika sekarang saya tambahkan satu bit untuk akhir nomor, seperti ini: 100010101010111 Runtime akan sekarang (kasus terburuk) menjadi 2T. Saya dapat melipatgandakan jumlah pekerjaan algoritma tidak hanya dengan menambahkan satu lebih sedikit! Algoritma berjalan di pseudopolynomial waktu jika runtime adalah beberapa polinomial dalam nilai numerik dari masukan, daripada dalam jumlah bit yang diperlukan untuk merepresentasikan hal itu. Kami perdana pengujian algoritma adalah pseudopolynomial waktu algoritma, karena berjalan dalam waktu O(n4), tapi itu's tidak polynomial-time algorithm karena sebagai fungsi dari jumlah bit x yang diperlukan untuk menulis input, runtime adalah O(24x). Alasan bahwa "bilangan PRIMA adalah P" kertas itu begitu signifikan adalah bahwa runtime adalah (kira-kira) O(log12 n), yang sebagai fungsi dari jumlah bit adalah O(x12). Jadi mengapa ini penting? Nah, kami memiliki banyak pseudopolynomial waktu algoritma untuk memfaktorkan bilangan bulat. Namun, algoritma ini, secara teknis, eksponensial-waktu algoritma. Hal ini sangat berguna untuk kriptografi: jika anda ingin menggunakan enkripsi RSA, anda harus mampu untuk percaya bahwa kita dapat't faktor angka dengan mudah. Dengan meningkatkan jumlah bit dalam bilangan dengan nilai yang sangat besar (katakanlah, 1024 bit), anda dapat membuat jumlah waktu yang pseudopolynomial-waktu anjak piutang algoritma harus mengambil begitu besar bahwa itu akan benar-benar dan benar-benar tidak layak untuk faktor angka-angka. Jika, di sisi lain, kita dapat menemukan polinomial-waktu anjak piutang algoritma, ini isn't selalu terjadi. Menambahkan lebih banyak bit dapat menyebabkan pekerjaan bertambah banyak, tetapi pertumbuhan hanya akan polinomial pertumbuhan, bukan pertumbuhan eksponensial. Mengatakan bahwa, dalam banyak kasus pseudopolynomial waktu algoritma yang baik-baik saja karena ukuran dari angka-angka tidak't terlalu besar. Misalnya, menghitung semacam memiliki runtime O(n + U), dimana U adalah jumlah terbesar dalam array. Ini adalah pseudopolynomial waktu (karena nilai numerik U memerlukan O(log U) bit untuk menulis, sehingga runtime adalah eksponensial dalam ukuran input). Jika kita artifisial membatasi U sehingga U isn't terlalu besar (katakanlah, jika kita membiarkan U 2), maka runtime adalah O(n), yang sebenarnya jumlahnya banyak waktu. Ini adalah cara radix sort karya: dengan pengolahan angka satu bit pada suatu waktu, runtime setiap putaran adalah O(n), sehingga secara keseluruhan runtime adalah O(n log U). Ini benar-benar adalah ** jumlahnya banyak waktu, karena menulis n nomor urut menggunakan Ω(n) bit dan nilai dari log U berbanding lurus dengan jumlah bit yang diperlukan untuk menulis nilai maksimum dalam array. Harap ini membantu!
Pseudo-polinomial kompleksitas waktu polinomial berarti nilai/besarnya input tetapi eksponensial dalam ukuran input.
Dengan ukuran kita berarti jumlah bit yang diperlukan untuk menulis input.
Dari pseudo-code dari ransel, kita dapat menemukan kompleksitas waktu untuk menjadi O(nW).
// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n) //
Knapsack capacity (W)
for w from 0 to W
do m[0, w] := 0
end for
for i from 1 to n do
for j from 0 to W do
if j >= w[i] then
m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
else
m[i, j] := m[i-1, j]
end if
end for
end for
Di sini, W tidak polinomial dalam panjang input meskipun, yang adalah apa yang membuatnya pseudo-polinomial.
Let s be jumlah bit yang diperlukan untuk merepresentasikan W
i.e. size of input= s =log(W) (log= log base 2)
-> 2^(s)=2^(log(W))
-> 2^(s)=W (because 2^(log(x)) = x)
Sekarang, waktu berjalan ransel
= O(nW) = O(n * 2^s)
yang tidak polinomial.