analisis waktu algoritma “ukuran input” vs “elemen input”

Saya masih sedikit bingung dengan istilah "panjang input" dan "ukuran input" ketika digunakan untuk menganalisis dan menggambarkan batas atas asimptomatik untuk suatu algoritma

Sepertinya panjang input untuk algoritme tergantung banyak jenis data dan algoritme yang Anda bicarakan.

Beberapa penulis merujuk pada panjang input dengan ukuran karakter yang diperlukan untuk mewakili input, jadi "abcde" jika digunakan sebagai input yang ditetapkan dalam suatu algoritma akan memiliki "panjang input" 6 karakter.

Jika bukan karakter kami memiliki nomor (bilangan bulat misalnya) maka kadang-kadang representasi biner adalah penggunaan bukan karakter sehingga "panjang input" dihitung sebagai (Being L nomor Max pada input set) . $N*log(L)$

Ada masalah lain yang bahkan jika set input adalah angka, mereka menggambarkan "panjang input" sebagai "variabel keputusan", jadi untuk set input panjang N dengan angka dalam kisaran panjang input hanya N ( subset sum misalnya), atau bahkan lebih menyulitkan jumlah tempat nilai-nilai biner yang dibutuhkan untuk menyatakan masalah (apa yang saya percaya adalah sama seperti $0-2^{32}$ $N*log(L)$ )

Begitu:

itu tergantung pada algoritma?
Apa artinya dan kapan harus menggunakan setiap "versi" panjang input
Apakah ada beberapa aturan yang bisa saya gunakan untuk memutuskan mana yang akan digunakan?

complexity-theory terminology algorithm-analysis time-complexity runtime-analysis Jesus Salas
sumber

Dalam arti paling formal, ukuran input diukur mengacu pada implementasi algoritma Turing Machine, dan itu adalah jumlah simbol alfabet yang diperlukan untuk menyandikan input.

Ini tentu saja agak abstrak, dan sangat sulit untuk dikerjakan dalam praktiknya, atau setidaknya sangat menjengkelkan - kita perlu mempertimbangkan bagaimana kita akan menentukan pembatas dll. Dll. Apa yang terjadi secara normal dalam praktek adalah kita mencari sebuah proxy yang pengukuran ukuran input - sesuatu yang lebih nyaman dan mudah diakses, tapi itu tidak menimbulkan masalah matematika dalam analisis kami.

Dengan menggunakan contoh "abcde" Anda, biasanya alfabet yang kami gunakan untuk input kecil, sehingga meskipun menggunakan pengukuran proxy karakter, kami tahu bahwa bahkan pada Mesin Turing, kami dapat, jika kami merasa terganggu, tentukan pengkodean input yang akan mengubah "abcde" ke beberapa bentuk yang dikodekan yang memiliki panjang paling banyak untuk beberapa konstanta . Ekspansi oleh konstanta ini biasanya tidak akan membuat perbedaan dalam analisis asimptotik kami, karena kami secara rutin membuang faktor-faktor konstan. $5$ $5\times c$ $c$

Dalam kasus yang berbeda, kita sering mengukur ukuran grafik input dengan jumlah simpul . Jelas jika kita ingin menentukan grafik besar yang sewenang-wenang, ukuran input yang disandikan tidak hanya - apa yang terjadi pada tepi, misalnya? Apa yang kita ketahui adalah bahwa kita dapat menggunakan skema pengkodean yang masuk akal yang mewakili grafik dalam bit. Ini sedikit lebih ekspansi daripada konstan, tetapi dalam banyak kasus menarik, kita hanya berurusan dengan hal-hal di granularity polinomial, dan polinomial menyusun dengan baik dalam banyak cara - khususnya, sebagai contoh, jika kami menentukan bahwa waktu berjalan kami adalah $n$ $n$ $N = c\cdot n^{2}\log n$ mana adalah polinomial, maka kita tahu bahwa ada beberapa polinomial sehingga , jadi ketika kita kembali ke ukuran formal input , kami masih dalam polinomial. $O(p(n))$ $p$ $p'$ $O(p(n)) = O(p'(N))$

Tempat di mana ini mungkin jatuh adalah ketika Anda bekerja dengan angka. Karena angka dengan magnitudo dapat dikodekan dalam bit, jika waktu berjalan kami adalah , ini akan menjadi - eksponensial dalam ukuran input aktual - yang akan membuat besarnya adalah pilihan yang buruk untuk proxy untuk ukuran input jika kita ingin berbicara tentang keanggotaan dalam misalnya (ketika Anda datang ke Strongly - lengkap dan lemah - $m$ $n = O(\log m)$ $O(m)$ $O(2^{n})$ $m$ $\mathcal{P}$ $\mathcal{NP}$ $\mathcal{NP}$ -lengkap, ingat ini). Di sisi lain, jika kita hanya tertarik pada decidability, maka itu akan menjadi ukuran proxy yang cukup baik.

Jadi, sementara tidak ada aturan lain untuk memilih ukuran proksi untuk ukuran input, persyaratannya adalah bahwa ekspansi atau kontraksi ukuran proksi dibandingkan dengan ukuran input harus kompatibel dengan apa yang Anda coba buktikan. Sebagai aturan praktis, perubahan faktor konstan hampir tidak pernah menjadi masalah, faktor polinom kecil biasanya baik dan berfungsi untuk sebagian besar teori dasar yang Anda lihat, faktor polinom besar mungkin masih berfungsi dalam teori, tetapi bisa menjadi kejutan yang buruk dalam praktik, dan jumlah perubahan eksponensial biasanya terlalu ekstrim.

Luke Mathieson
sumber

Terima kasih atas jawabannya. Sangat menarik bagian yang Anda bicarakan tentang pemilihan proksi yang tepat untuk berbicara tentang keanggotaan dalam P atau NP untuk input, yang bisa menjadi pertanyaan baru yang lengkap! Selain itu, dan kembali ke pertanyaan sebelumnya. Mana yang menurut Anda akan menjadi proksi terbaik untuk suatu algoritma yang inputnya adalah satu set bilangan bulat? Saya kira Mungkin itu akan tergantung pada algoritma? Saya melihat 3 opsi potensial: N (menjadi panjang set) N * Log (L) (L menjadi nilai maksimal) dan Log (Jumlah (set)).

Jesus Salas

@ JesusSalas, itu pasti bisa bergantung pada apa yang Anda lakukan dengan mereka, tetapi

akan menjadi jawaban "cukup dekat dengan penyandian TM" yang paling sederhana, tetapi masih bisa menarik untuk melihat waktu berjalan dalam hal

, atau mungkin

dan besarnya jumlah terbesar - tentu saja ini hanya

, tetapi terkadang lebih mudah untuk menganalisis hal-hal dengan langkah-langkah yang tidak jelas.

N \log L

$N\log L$

N

$N$

N

$N$

2^{\log L}

$2^{\log L}$

Luke Mathies

Ini mencakup pangkalan tetapi ada beberapa ketidakakuratan. Mewakili "abcde" pada mesin Turing tidak membutuhkan

karakter

: dibutuhkan lima karakter jika Anda memilih alfabet yang tepat. Dan Anda tidak perlu

bit untuk mewakili grafik

-vertex: matriks adjacency persis

bit.

5 c

$5c$

c n^{2} \log n

$cn^2\log n$

n

$n$

n^{2}

$n^2$

David Richerby

Mungkin kapan menggunakan N atau N log L dapat bergantung pada biaya untuk algoritma untuk beroperasi pada setiap elemen input. Saya kira jika kita memiliki asumsi bahwa algoritma menggunakan waktu konstan untuk melakukan tugasnya pada setiap elemen input secara terpisah dari ukurannya dalam bit (dan ini tidak disalahgunakan), maka N mungkin yang benar, menghasilkan O (N) . Di sisi lain jika ukuran elemen input dalam bit meningkatkan biaya operasi maka N log L tampaknya lebih akurat karena kita harus menyatakan dalam batas atas properti apa dari input yang terlibat dalam pertumbuhan

Jesus Salas

@ DavidRicherby ya, jika Anda bisa memilih alfabet yang dibutuhkan

simbol, tapi ini hanya di mana

, jika karena alasan lain kami memiliki alfabet yang berbeda, katakan biner, mengingat jauh lebih berguna untuk bisa mengatakan kami dapat mengkodekan segala sesuatu di biner tanpa kehilangan umum, maka

, tapi mudah, dan menarik untuk melihat bahwa itu relatif mudah untuk melakukannya dengan setiap alfabet tidak-gila dalam faktor konstan

. Juga, benar, Anda mungkin tidak perlu

5

$5$

c = 1

$c=1$

c = \log_{2} 5

$c = \log_{2}5$

5

$5$

O (n^{2} \log n)

$O(n^{2}\log n)$ bit, tetapi itu adalah batas atas yang cukup kuat yang dapat menangani kedua penyandian normal.

Luke Mathieson

analisis waktu algoritma “ukuran input” vs “elemen input”

Jawaban: