Bagaimana kita dapat berasumsi bahwa operasi dasar pada angka membutuhkan waktu yang konstan?

74

Biasanya dalam algoritma kami tidak peduli tentang perbandingan, penambahan, atau pengurangan angka - kami menganggap mereka berjalan dalam waktu . Sebagai contoh, kita mengasumsikan ini ketika kita mengatakan bahwa pengurutan berbasis perbandingan adalah , tetapi ketika angka terlalu besar untuk masuk ke dalam register, kita biasanya mewakili mereka sebagai array sehingga operasi dasar memerlukan perhitungan tambahan per elemen. $O(1)$ $O(n\log n)$

Apakah ada bukti yang menunjukkan bahwa perbandingan dua angka (atau fungsi aritmatika primitif lainnya) dapat dilakukan dalam ? Jika tidak mengapa kita mengatakan bahwa penyortiran berbasis perbandingan adalah ? $O(1)$ $O(n\log n)$

Saya mengalami masalah ini ketika saya menjawab pertanyaan SO dan saya menyadari bahwa algoritma saya tidak karena cepat atau lambat aku harus berurusan dengan besar-int, itu juga tidak semu polinomial waktu algoritma, itu . $O(n)$ $P$

algorithms complexity-theory algorithm-analysis time-complexity reference-question Raphael
sumber

3

Jika Anda akan menghitung kerumitan membandingkan angka, Anda juga harus menuliskan batas kompleksitas Anda dalam hal ukuran bit input. Jadi diberi bit angka, ukuran bit dari input adalah dan pengurutan dapat dilakukan dalam waktu.

N

$N$

w

$w$

n = N w

$n=Nw$

O (N w \log N) = O (n \log n)

$O(Nw \log N) = O(n \log n)$

Sasho Nikolov

2

pada dasarnya ada dua "ranah" atau "rezim" studi kompleksitas. umumnya operasi diasumsikan untuk operasi "lebar tetap" yang merupakan perkiraan yang masuk akal untuk sebagian besar bahasa komputer yang memiliki representasi angka lebar tetap termasuk untuk floating point misalnya 2-4 byte (lihat misalnya standar IEEE). kemudian ada "aritmatika presisi sewenang-wenang" di mana angka memiliki ukuran sewenang-wenang dan ada studi yang lebih cermat / tepat tentang kompleksitas operasi. konteks yang pertama lebih pada analisis terapan & yang terakhir lebih pada analisis teoretis / abstrak.

O (1)

$O(1)$

vzn

75

Bagi orang-orang seperti saya yang mempelajari algoritma untuk mencari nafkah, model komputasi standar abad ke-21 adalah integer RAM . Model ini dimaksudkan untuk mencerminkan perilaku komputer nyata lebih akurat daripada model mesin Turing. Komputer dunia nyata memproses bilangan bulat banyak-bit dalam waktu konstan menggunakan perangkat keras paralel; bukan bilangan bulat sembarang , tetapi (karena ukuran kata tumbuh dengan mantap dari waktu ke waktu) juga bukan bilangan bulat ukuran tetap .

Model tergantung pada satu parameter , yang disebut ukuran kata . Setiap alamat memori memiliki integer bit tunggal , atau kata . Dalam model ini, ukuran input adalah jumlah kata dalam input, dan waktu berjalan suatu algoritma adalah jumlah operasi pada kata-kata . Operasi aritmatika standar (penambahan, pengurangan, perkalian, pembagian bilangan bulat, sisanya, perbandingan) dan operasi boolean (bitwise dan, atau, xor, shift, rotate) pada kata-kata memerlukan waktu menurut definisi . $w$ $w$ $n$ $O(1)$

Secara formal, ukuran kata adalah TIDAK konstan $w$ untuk tujuan menganalisis algoritma dalam model ini. Untuk membuat model konsisten dengan intuisi, kita memerlukan , karena jika tidak kita bahkan tidak dapat menyimpan integer dalam satu kata. Namun demikian, untuk sebagian besar algoritma non-numerik, waktu berjalan sebenarnya independen dari , karena algoritma tersebut tidak peduli dengan representasi biner yang mendasari input mereka. Mergesort dan heapsort keduanya berjalan dalam waktu ; median-of-3-quicksort berjalan dalam waktu dalam kasus terburuk. Satu pengecualian penting adalah jenis radix biner, yang berjalan dalam waktu . $w \ge \log_2 n$ $n$ $w$ $O(n\log n)$ $O(n^2)$ $O(nw)$

Pengaturan memberi kita model RAM biaya logaritmik tradisional. Tetapi beberapa algoritma integer RAM dirancang untuk ukuran kata yang lebih besar, seperti algoritma pengurutan integer linear-waktu dari Andersson et al. , yang membutuhkan . $w = \Theta(\log n)$ $w = \Omega(\log^{2+\varepsilon} n)$

Untuk banyak algoritme yang muncul dalam praktiknya, ukuran kata sama sekali bukan masalah, dan kita dapat (dan memang) kembali pada model RAM seragam yang jauh lebih sederhana. Satu-satunya kesulitan yang serius berasal dari perkalian bersarang, yang dapat digunakan untuk membangun sangat bilangan bulat besar sangat cepat. Jika kita dapat melakukan aritmatika pada bilangan bulat sewenang-wenang dalam waktu konstan, kita dapat menyelesaikan masalah di PSPACE dalam waktu polinomial . $w$

Pembaruan: Saya juga harus menyebutkan bahwa ada pengecualian pada "model standar", seperti algoritma pengganda integer Fürer , yang menggunakan mesin Turing multitape (atau setara, "bit RAM"), dan sebagian besar algoritma geometris, yang dianalisis secara teoritis model "RAM nyata" yang bersih namun ideal .

Ya, ini adalah sekaleng cacing.

JeffE
sumber

3

Saya tahu saya seharusnya memilih, tetapi saya tidak bisa berhenti mengatakannya: Ini adalah jawaban terbaik. Kuncinya adalah bahwa (1) operasi aritmatika adalah waktu yang konstan menurut definisi dan tidak apa-apa karena secara teori Anda dapat memilih model apa pun, dan (2) Anda harus memiliki beberapa alasan untuk memilih model tertentu, dan jawaban ini menjelaskan apa itu.

rgrig

Saya setuju dengan rgig, (Juga saya seharusnya memilih), tetapi sedikit masalah adalah ukuran input tidak terkait dengan angka input, mis. Jika saya memiliki

input nomor terbesar saya adalah

, dan jika saya memilih model perhitungan seperti yang saya suka, ini menyebabkan algoritma waktu polinomial semu menjadi

, apakah saya benar?

n

$n$

m

$m$

P

$P$

1

Jika input Anda terdiri dari angka-angka dengan lebih dari

bit, maka agar sesuai dengan model Anda harus membaginya menjadi potongan-potongan

bit, seperti dalam kehidupan nyata. Misalnya, jika input Anda terdiri dari

bilangan bulat antara

dan

, maka ukuran input Anda yang sebenarnya adalah

. Jadi, waktu menjalankan pseudo-polinomial seperti waktu

masih eksponensial dalam ukuran input ketika

besar.

w

$w$

w

$w$

N

$N$

0

$0$

M

$M$

N \log_{w} M = (N \lg M) / (\lg w)

$N\log_w M = (N\lg M)/(\lg w)$

O (N M)

$O(NM)$

M

$M$

JeffE

Apakah ada algoritma yang dianalisis dalam model RAM Nyata yang tidak diam-diam algoritma "Tipe RAM"? Saya tidak pernah terlalu memikirkannya, tetapi tidak dapat dengan cepat menghasilkan contoh yang tidak.

Louis

1

@ Louis: Ya, banyak: diagram Voronoi, jalur terpendek Euclidean, stek rekursif, pohon partisi simplisial, .... Tapi contoh terbaiknya adalah eliminasi Gaussian, yang berjalan dalam waktu

pada model RAM nyata (atau RAM integer unit-cost, tetapi membutuhkan waktu

pada RAM integer

O (n^{3})

$O(n^3)$

O (n^{4})

$O(n^4)$

JeffE

24

Itu tergantung pada konteksnya. Ketika berhadapan dengan kompleksitas algoritma level bit , kami tidak mengatakan bahwa penambahan dua angka bit adalah , kami mengatakan itu adalah . Demikian pula untuk multiplikasi dll. $n$ $O(1)$ $O(n)$

Massimo Cafaro
sumber

Dari artikel Anda yang direferensikan: "dapat diukur dengan dua cara yang berbeda: satu dalam hal bilangan bulat yang diuji atau dikalikan, dan satu dalam hal jumlah digit biner (bit) dalam bilangan bulat", tetapi ini tidak benar, kami harus selalu diukur berdasarkan ukuran input.

1

@ SaeedAmiri: itu hanya tergantung pada pengkodean yang digunakan. Dalam artikel itu, misalnya, jika input adalah bilangan bulat

ditentukan menggunakan pengkodean unary, divisi sidang akan hanya membutuhkan

. Ini jumlahnya banyak dalam ukuran input! Apakah ini berarti bahwa anjak piutang oleh divisi sidang ada di

? Tidak, algoritmanya pseudo-polinomial . Menggunakan pengkodean biner umum, Anda mendapatkan algoritma eksponensial, lagi-lagi dalam ukuran input. Seperti yang dinyatakan, ini terjadi karena jumlah bit dalam input

telah menjadi lebih kecil secara eksponensial mengubah penyandiannya.

n

$n$

θ (n^{1 / 2})

$\theta(n^{1/2})$

P

$P$

n

$n$

Massimo Cafaro

Omong-omong, algoritma pseudo-polinomial sebenarnya berguna, jika urutan besarnya parameter mereka dalam contoh aktual cukup rendah. Contoh yang paling terkenal mungkin adalah algoritma pseudo-polinomial untuk memecahkan masalah ransel.

Massimo Cafaro

Pertama saya harus menyebutkan bahwa halaman wiki yang dirujuk Anda tidak baik karena tidak memiliki referensi yang baik, Juga saya tidak tahu mengapa Anda pikir saya sedang berbicara tentang algoritma waktu pseudo-polinomial, mungkin karena ukuran input biasanya buttleneck dalam hal ini? tapi saya tidak berbicara tentang mereka, saya berbicara sebagian besar tentang masalah yang ada di

bahkan dengan asumsi ukuran input, seperti menyortir, lagi pula karena kita tidak bisa curang dan mengatakan masalah NPC ada di

Saya pikir kita tidak seharusnya katakanlah sortasi adalah

kecuali kami memiliki bukti formal untuk mengabaikan perbandingan.

P

$P$

P

$P$

O (n \log n)

$O(n \log n)$

Saya sedang membahas algoritma pseudo-polinomial untuk memusatkan perhatian Anda pada ukuran input, untuk menunjukkan kepada Anda bahwa itu bisa menyesatkan. Ini adalah contoh lain. Anda diberi nomor alami sebagai input, misalkan

, dan algoritme menjalankan loop di mana ia melakukan operasi waktu

untuk

iterasi. Kompleksitas dari algoritma loop sederhana ini diukur sebagai fungsi dari ukuran input, adalah

. Karena

n

$n$

O (1)

$O(1)$

n

$n$

O (n) = O (2^{l g n})

$O(n) = O(2^{lg n})$

l g n

$lg n$ adalah ukuran input, algoritmanya eksponensial dalam ukuran input! Pikirkan tentang ini. Sekarang Anda mungkin mengerti apa yang saya maksud dengan "Itu hanya tergantung pada konteksnya".

Massimo Cafaro

16

Untuk menjawab pertanyaan sebagaimana dinyatakan: algoritme cukup melakukannya, cukup sering, dengan menggunakan model RAM. Untuk menyortir, dalam banyak kasus, orang bahkan menganalisis model perbandingan yang lebih sederhana , yang saya bahas sedikit lebih dalam jawaban terkait.

Untuk menjawab pertanyaan implisit tentang mengapa mereka melakukannya: Saya akan mengatakan bahwa model ini memiliki daya prediksi yang cukup baik untuk beberapa jenis algoritma kombinatorial, di mana angkanya semua "kecil" dan, pada mesin nyata, cocok dengan register.

Untuk menjawab tindak lanjut tersirat tentang algoritma numerik: Tidak, model RAM lama yang biasa bukan standar di sini. Bahkan eliminasi Gaussian dapat membutuhkan perawatan. Biasanya, untuk perhitungan peringkat, Lemma Schwartz akan masuk (misalnya, Bagian 5 di sini ). Contoh kanonik lainnya adalah analisis Algoritma Ellipsoid, yang membutuhkan kehati - hatian untuk dianalisis.

Dan akhirnya: Orang-orang telah memikirkan penyortiran string sebelumnya , bahkan baru-baru ini.

Pembaruan: Masalah dengan pertanyaan ini adalah bahwa "kami" dan "menganggap" tidak ditentukan secara tepat. Saya akan mengatakan bahwa orang-orang yang bekerja dalam model RAM tidak melakukan algoritma numerik atau teori kompleksitas (di mana menentukan kompleksitas pembagian adalah hasil yang dirayakan ).

Louis
sumber

Hmmmm, sepertinya ini jawaban yang menarik ....

Apakah ada alasan mengapa itu tidak sepenuhnya menjawab pertanyaan?

Louis

7

Saya tidak dapat menemukan studi ini, tetapi Kozen mengatakan dalam pengantar "Desain dan Analisis Algoritma" bahwa model "mencerminkan pengamatan eksperimental yang lebih akurat [daripada model log-cost] untuk data moderat ukuran (karena perkalian benar-benar membutuhkan satu unit waktu). " Dia juga memberikan referensi pada makalah ini sebagai contoh bagaimana model dapat disalahgunakan. $O(1)$ $O(1)$

Ini benar-benar bukan evaluasi legit (paling tidak karena itu Python), tapi inilah beberapa nomor dari berjalan python -mtimeit "$a * $b"untuk $adi dan . (Saya berhenti di 66 karena sintaksis Python berhenti menerima integer literal dan saya harus sedikit mengganti kode evaluasi saya, jadi saya tidak.: P) $10^{\{1,2,...,66\}}$ $b = 2*$a

$10^{50}$ $\log_{10}(\tt{sys.maxint})$

Dougal
sumber

O (n)

$O(n)$

O (n \cdot \log n \cdot \log m)

$O(n \cdot \log n \cdot \log m)$

7

$O(1)$

$O(\log M)$ $O (N \log N)$ $O (N \log N \log M)$

$M$

Erel Segal-Halevi
sumber

O (\log m)

$O(\log m)$

O (\log n)

$O(\log n)$

m

$m$

O (l o g N)

$O(log N)$

n

$n$

n^{n^{n}}

$n^{n^n}$

Anda benar, saya mengoreksi jawaban saya.

Erel Segal-Halevi

4

Saya akan mengatakan bahwa kita biasanya mengasumsikan O (1) operasi aritmatika karena kita biasanya melakukan hal-hal dalam konteks bilangan bulat 32-bit atau bilangan bulat 64-bit atau angka floating point IEEE 754. O (1) mungkin merupakan pendekatan yang cukup bagus untuk jenis aritmatika tersebut.

Tetapi secara umum, itu tidak benar. Secara umum Anda membutuhkan algoritma untuk melakukan penjumlahan, pengurangan, perkalian, dan pembagian. Boolos, Burgess and Jefferies ' Computability and Logic muncul dalam pikiran sebagai cara untuk memahami bukti dari itu, dalam hal beberapa sistem formal yang berbeda, Fungsi Rekursif dan Mesin Abacus, setidaknya, dalam salinan Edisi ke-4 saya.

Anda dapat melihat istilah lambda-calculus untuk pengurangan dan pembagian dengan Angka Gereja untuk penjelasan yang mudah dilihat mengapa kedua operasi itu bukan O (1). Agak sulit untuk melihat penambahan dan penggandaan serta eksponensial, tetapi ada di sana jika Anda mempertimbangkan bentuk Angka Gereja sendiri.

Bruce Ediger
sumber

Bagaimana kita dapat berasumsi bahwa operasi dasar pada angka membutuhkan waktu yang konstan?

Jawaban: