Mengukur kos pengiraan

Seterusnya, kita akan bincangkan rangka kerja matematik untuk mengukur kos pengiraan, yang difokuskan khusus kepada keperluan kursus ini. Analisis algoritma dan kerumitan pengiraan adalah bidang kajian tersendiri, dan mempunyai banyak lagi perkara untuk diperkatakan mengenai konsep-konsep ini.

Sebagai titik permulaan, perhatikan rajah berikut dari pelajaran sebelumnya, yang mewakili abstraksi peringkat tinggi bagi sebuah pengiraan.

Pengiraan itu sendiri boleh dimodelkan atau dihuraikan dengan pelbagai cara, seperti program komputer yang ditulis dalam Python, mesin Turing, Circuit Boolean, atau Circuit kuantum. Fokus kita akan tertumpu pada Circuit (kedua-dua Boolean dan kuantum).

Pengekodan dan panjang input

Mari mulakan dengan input dan output bagi masalah pengiraan, yang kita andaikan sebagai rentetan binari. Simbol-simbol lain boleh digunakan, tetapi kita akan memudahkan perkara dengan membataskan perhatian pada input dan output berupa rentetan binari. Melalui rentetan binari, kita boleh mengekod pelbagai objek menarik yang berkaitan dengan masalah yang ingin kita selesaikan, seperti nombor, vektor, matriks, dan graf, serta senarai objek-objek ini dan yang lain.

Sebagai contoh, untuk mengekod integer bukan negatif, kita boleh menggunakan notasi binari. Jadual berikut menyenaraikan pengekodan binari bagi sembilan integer bukan negatif pertama, bersama panjang (bermaksud jumlah bilangan bit) bagi setiap pengekodan.

Nombor	Pengekodan binari	Panjang
0	0	1
1	1	1
2	10	2
3	11	2
4	100	3
5	101	3
6	110	3
7	111	3
8	1000	4

Kita boleh dengan mudah memperluaskan pengekodan ini untuk menangani integer positif dan negatif dengan menambahkan bit tanda pada perwakilan jika kita mahu. Kadang-kadang juga mudah untuk membenarkan perwakilan binari bagi integer bukan negatif mempunyai sifar pendahulu, yang tidak mengubah nilai yang dikodkan tetapi membolehkan perwakilan memenuhi rentetan atau perkataan bersaiz tetap.

Menggunakan notasi binari untuk mewakili integer bukan negatif adalah perkara biasa dan cekap, tetapi jika kita mahu, kita boleh memilih cara lain untuk mewakili integer bukan negatif menggunakan rentetan binari, seperti yang dicadangkan dalam jadual berikut. Butiran khusus bagi alternatif-alternatif ini tidak penting dalam perbincangan ini — tujuannya hanyalah untuk menjelaskan bahawa kita memang mempunyai pilihan untuk pengekodan yang kita gunakan.

Nombor	Pengekodan unari	Pengekodan leksikografi
0	$\varepsilon$	$\varepsilon$
1	0	0
2	00	1
3	000	00
4	0000	01
5	00000	10
6	000000	11
7	0000000	000
8	00000000	001

(Dalam jadual ini, simbol $\varepsilon$ mewakili rentetan kosong, yang tidak mempunyai sebarang simbol dan panjangnya sama dengan sifar. Secara semula jadi, untuk mengelakkan kekeliruan yang jelas, kita menggunakan simbol khas seperti $\varepsilon$ untuk mewakili rentetan kosong dan bukannya benar-benar tidak menulis apa-apa.)

Jenis input lain, seperti vektor dan matriks, atau objek yang lebih rumit seperti huraian molekul, juga boleh dikodkan sebagai rentetan binari. Sama seperti yang kita lakukan untuk integer bukan negatif, pelbagai skim pengekodan yang berbeza boleh dipilih atau dicipta. Untuk sebarang skim yang kita reka untuk mengekod input bagi masalah tertentu, kita mentafsirkan panjang suatu rentetan input sebagai mewakili saiz contoh masalah yang sedang diselesaikan.

Sebagai contoh, bilangan bit yang diperlukan untuk menyatakan integer bukan negatif $N$ dalam notasi binari, yang kadang-kadang dilambangkan $\operatorname{lg}(N),$ diberikan oleh formula berikut.

$$\operatorname{lg}(N) = \begin{cases} 1 & N = 0\\ 1 + \lfloor \log_2 (N) \rfloor & N \geq 1 \end{cases}$$

Dengan mengandaikan kita menggunakan notasi binari untuk mengekod input kepada masalah pemfaktoran integer, panjang input untuk nombor $N$ ialah $\operatorname{lg}(N).$ Perlu diperhatikan, khususnya, bahawa panjang (atau saiz) input $N$ bukanlah $N$ itu sendiri; apabila $N$ besar, kita tidak memerlukan bilangan bit sebanyak itu untuk menyatakan $N$ dalam notasi binari.

Dari sudut pandang formal yang ketat, setiap kali kita mempertimbangkan masalah atau tugas pengiraan, hendaklah difahami bahawa skim khusus telah dipilih untuk mengekod objek-objek yang diberikan sebagai input atau dihasilkan sebagai output. Ini membolehkan pengiraan yang menyelesaikan masalah menarik dilihat secara abstrak sebagai transformasi daripada input rentetan binari kepada output rentetan binari.

Butiran tentang cara objek dikodkan sebagai rentetan binari semestinya penting untuk pengiraan-pengiraan ini pada suatu tahap. Namun biasanya, kita tidak terlalu risau tentang butiran-butiran ini apabila menganalisis kos pengiraan, supaya kita dapat mengelakkan diri daripada terperangkap dalam butiran yang kurang penting. Pemikiran asasnya ialah kita menjangkakan kos pengiraan untuk menukar antara skim pengekodan yang "munasabah" adalah tidak signifikan berbanding dengan kos menyelesaikan masalah sebenar. Dalam situasi di mana ini tidak berlaku, butiran tersebut boleh (dan sepatutnya) dijelaskan.

Sebagai contoh, pengiraan yang sangat mudah menukarkan antara perwakilan binari integer bukan negatif dan pengekodan leksikografinya (yang tidak kita jelaskan secara terperinci, tetapi boleh disimpulkan daripada jadual di atas). Atas sebab ini, kos pengiraan pemfaktoran integer tidak akan berbeza secara signifikan jika kita memutuskan untuk beralih daripada menggunakan salah satu pengekodan ini kepada yang lain untuk input $N.$ Sebaliknya, mengekod integer bukan negatif dalam notasi unari mengakibatkan peningkatan eksponen dalam jumlah simbol yang diperlukan, dan kita tidak akan menganggapnya sebagai skim pengekodan yang "munasabah" atas sebab ini.

Operasi asas

Sekarang mari kita pertimbangkan pengiraan itu sendiri, yang diwakili oleh segi empat biru dalam rajah di atas. Cara kita mengukur kos pengiraan adalah dengan mengira bilangan operasi asas yang diperlukan oleh setiap pengiraan. Secara intuitif, operasi asas adalah operasi yang melibatkan bilangan kecil dan tetap bit atau Qubit, yang boleh dilakukan dengan cepat dan mudah — seperti mengira AND bagi dua bit. Sebaliknya, menjalankan fungsi factorint tidak boleh dianggap secara munasabah sebagai operasi asas.

Secara formal, terdapat pilihan berbeza untuk apa yang merupakan operasi asas bergantung pada model pengiraan yang digunakan. Fokus kita akan tertumpu pada model Circuit, khususnya Circuit kuantum dan Boolean.

Set Gate sejagat

Untuk model pengiraan berasaskan Circuit, adalah lazim bahawa setiap Gate dilihat sebagai operasi asas. Ini membawa kepada persoalan tentang Gate yang mana yang kita benarkan dalam Circuit kita. Fokus buat masa ini pada Circuit kuantum, kita telah melihat beberapa Gate setakat ini dalam siri ini, termasuk Gate $X,$ $Y,$ $Z,$ $H,$ $S,$ dan $T,$ Gate swap, versi terkawal Gate (termasuk controlled-NOT, Toffoli, dan Fredkin), serta Gate yang mewakili pengukuran asas standard. Dalam konteks permainan CHSH kita juga melihat beberapa Gate putaran tambahan.

Kita juga membincangkan Gate pertanyaan dalam konteks model pertanyaan, dan kita juga melihat bahawa sebarang operasi unitari $U,$ yang bertindak ke atas sebarang bilangan Qubit, boleh dilihat sebagai Gate jika kita mahu — tetapi kita akan mengabaikan kedua-dua pilihan ini untuk tujuan perbincangan ini. Kita tidak akan bekerja dalam model pertanyaan (walaupun pelaksanaan Gate pertanyaan menggunakan operasi asas dibincangkan kemudian dalam pelajaran), dan melihat Gate unitari arbitrari, yang berpotensi bertindak ke atas jutaan Qubit, sebagai operasi asas tidak membawa kepada konsep kos pengiraan yang bermakna atau realistik.

Dengan tetap menggunakan Gate kuantum yang beroperasi pada bilangan Qubit yang kecil, satu pendekatan untuk memutuskan mana yang dianggap asas adalah dengan mencari kriteria yang tepat — tetapi ini bukan pendekatan standard atau yang akan kita ambil. Sebaliknya, kita hanya membuat pilihan.

Berikut adalah satu pilihan standard, yang akan kita gunakan sebagai set Gate lalai untuk Circuit kuantum:

• Gate unitari satu-Qubit daripada senarai ini: $X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T,$ dan $T^{\dagger}$
• Gate Controlled-NOT
• Pengukuran asas standard satu-Qubit

Alternatif umum adalah untuk memandang Gate Toffoli, Hadamard, dan $S$ sebagai asas, di samping pengukuran asas standard. Kadang-kadang semua Gate satu-Qubit dilihat sebagai asas, walaupun ini memang membawa kepada model yang tidak realistik kuatnya apabila ketepatan pelaksanaan Gate tidak diambil kira dengan betul.

Gate unitari dalam koleksi lalai kita membentuk apa yang dipanggil set Gate sejagat. Ini bermaksud kita boleh menganggarkan sebarang operasi unitari ke atas sebarang bilangan Qubit sehingga sebarang darjah ketepatan yang kita inginkan, menggunakan Circuit yang terdiri daripada Gate-Gate ini sahaja. Untuk lebih jelas, definisi keuniversalan tidak meletakkan sebarang keperluan pada kos penghampiran sedemikian, bermaksud bilangan Gate daripada set kita yang kita perlukan. Memang, hujah yang agak mudah berdasarkan konsep matematik ukuran mendedahkan bahawa kebanyakan operasi unitari mesti mempunyai kos yang sangat tinggi. Membuktikan keuniversalan set Gate kuantum bukan perkara mudah dan tidak akan diliputi dalam kursus ini.

Untuk Circuit Boolean, kita akan menggunakan Gate AND, OR, NOT, dan FANOUT sebagai yang mewakili operasi asas. Sebenarnya kita tidak memerlukan kedua-dua Gate AND dan Gate OR — kita boleh menggunakan hukum De Morgan untuk menukar daripada salah satu kepada yang lain dengan meletakkan Gate NOT pada semua tiga wayar input/output — tetapi bagaimanapun adalah lazim dan mudah untuk membenarkan kedua-dua Gate AND dan OR. Gate AND, OR, NOT, dan FANOUT membentuk set sejagat untuk pengiraan deterministik, bermaksud bahawa sebarang fungsi daripada sebarang bilangan tetap bit input kepada sebarang bilangan tetap bit output boleh dilaksanakan dengan Gate-Gate ini.

Prinsip pengukuran tertangguh

Gate pengukuran asas standard boleh muncul dalam Circuit kuantum, tetapi kadang-kadang mudah untuk menangguhkannya hingga ke penghujung. Ini membolehkan kita melihat pengiraan kuantum sebagai terdiri daripada bahagian unitari (mewakili pengiraan itu sendiri), diikuti oleh fasa pembacaan mudah di mana Qubit diukur dan hasilnya dikeluarkan. Ini sentiasa boleh dilakukan, dengan syarat kita sanggup menambah Qubit tambahan untuk setiap pengukuran asas standard. Dalam rajah berikut, Circuit di sebelah kanan menggambarkan bagaimana ini boleh dilakukan untuk Gate di sebelah kiri.

Secara khususnya, bit klasik dalam Circuit di sebelah kiri digantikan oleh Qubit di sebelah kanan (dimulakan ke keadaan $\vert 0\rangle$), dan pengukuran asas standard digantikan oleh Gate controlled-NOT, diikuti oleh pengukuran asas standard pada Qubit bawah. Intinya ialah pengukuran asas standard dalam Circuit sebelah kanan boleh ditolak ke penghujung Circuit. Jika bit klasik dalam Circuit di sebelah kiri kemudiannya digunakan sebagai bit kawalan, kita boleh menggunakan Qubit bawah dalam Circuit di sebelah kanan sebagai kawalan, dan kesan keseluruhannya akan sama. (Kita mengandaikan bahawa bit klasik dalam Circuit di sebelah kiri tidak ditimpa selepas pengukuran berlaku oleh pengukuran lain — tetapi jika berlaku, kita sentiasa boleh menggunakan bit klasik baru dan bukannya menimpa yang telah digunakan untuk pengukuran sebelumnya.)

Saiz dan kedalaman Circuit

Saiz Circuit

Jumlah bilangan Gate dalam Circuit dirujuk sebagai saiz Circuit tersebut. Oleh itu, dengan mengandaikan bahawa Gate dalam Circuit kita mewakili operasi asas, saiz Circuit mewakili bilangan operasi asas yang diperlukan — atau, dalam erti kata lain, kos pengiraan nya. Kita tulis $\operatorname{size}(C)$ untuk merujuk kepada saiz Circuit $C$ yang diberikan.

Sebagai contoh, pertimbangkan Circuit Boolean berikut untuk mengira XOR bagi dua bit.

Saiz Circuit ini ialah 7 kerana terdapat 7 Gate secara keseluruhannya. (Operasi Fanout tidak selalu dikira sebagai Gate, tetapi bagi tujuan pelajaran ini kita akan mengiranya sebagai Gate.)

Masa, kos, dan kedalaman Circuit

Masa adalah sumber yang sangat penting, atau kekangan yang membatasi, untuk pengiraan. Contoh-contoh di atas, seperti tugas memfaktorkan RSA1024, mengukuhkan pandangan ini. Fungsi factorint tidak gagal memfaktorkan RSA1024 sebenarnya, cuma kita tidak mempunyai masa yang cukup untuk membiarkannya selesai.

Konsep kos pengiraan, sebagai bilangan operasi asas yang diperlukan untuk melaksanakan pengiraan, bertujuan menjadi proksi abstrak untuk masa yang diperlukan untuk melaksanakan pengiraan. Setiap operasi asas memerlukan sejumlah masa untuk dilaksanakan, dan semakin banyak operasi asas yang diperlukan oleh pengiraan, semakin lama masa yang diperlukan, sekurang-kurangnya secara umum. Demi kesederhanaan, kita akan terus membuat kaitan antara kos pengiraan dengan masa yang diperlukan untuk menjalankan algoritma.

Tetapi perhatikan bahawa saiz Circuit tidak semestinya berkoresponden secara langsung dengan berapa lama masa yang diperlukan untuk dijalankan. Dalam Circuit Boolean kita untuk mengira XOR bagi dua bit, misalnya, kedua-dua Gate FANOUT boleh dilakukan serentak, begitu juga kedua-dua Gate NOT, serta kedua-dua Gate AND. Cara lain untuk mengukur kecekapan Circuit, yang mengambil kira kemungkinan pemprosesan selari ini, ialah melalui kedalaman nya. Ini adalah bilangan minimum lapisan Gate yang diperlukan dalam Circuit, di mana Gate dalam setiap lapisan beroperasi pada wayar yang berbeza. Secara setara, kedalaman Circuit ialah bilangan maksimum Gate yang ditemui pada sebarang laluan dari wayar input ke wayar output. Untuk Circuit di atas, misalnya, kedalamannya ialah 4.

Kedalaman Circuit adalah satu cara untuk memformalkan masa larian bagi pengiraan selari. Ini adalah topik lanjutan, dan terdapat pembinaan Circuit yang sangat canggih yang diketahui untuk meminimumkan kedalaman yang diperlukan bagi pengiraan tertentu. Terdapat juga beberapa soalan menarik yang masih belum terjawab berkenaan kedalaman Circuit. (Sebagai contoh, banyak yang masih tidak diketahui tentang kedalaman Circuit yang diperlukan untuk mengira GCD.) Kita tidak akan banyak lagi membicarakan tentang kedalaman Circuit dalam siri ini, selain daripada memasukkan beberapa fakta menarik mengenai kedalaman Circuit sepanjang perjalanan, tetapi hendaklah diakui dengan jelas bahawa pemprosesan selari adalah sumber potensi kelebihan pengiraan.

Menugaskan kos berbeza kepada Gate yang berbeza

Satu nota akhir berkenaan saiz Circuit dan kos pengiraan ialah adalah mungkin untuk menugaskan kos berbeza kepada Gate, dan bukannya memandang setiap Gate menyumbang sama rata kepada jumlah kos.

Sebagai contoh, seperti yang telah disebutkan, Gate FANOUT sering dianggap percuma untuk Circuit Boolean — bermaksud kita boleh memilih Gate FANOUT mempunyai kos sifar. Sebagai contoh lain, apabila kita bekerja dalam model pertanyaan dan mengira bilangan pertanyaan yang dibuat oleh Circuit kepada fungsi input (dalam bentuk kotak hitam), kita secara efektifnya menugaskan kos satu unit kepada Gate pertanyaan dan kos sifar kepada Gate lain, seperti Gate Hadamard. Contoh terakhir ialah kita kadang-kadang menugaskan kos berbeza kepada Gate bergantung pada betapa sukarnya untuk dilaksanakan, yang boleh berbeza-beza bergantung pada perkakasan yang dipertimbangkan.

Walaupun semua pilihan ini munasabah dalam konteks yang berbeza, untuk pelajaran ini kita akan memudahkan dan berpegang pada saiz Circuit sebagai perwakilan kos pengiraan.

Kos sebagai fungsi panjang input

Kita terutamanya berminat dengan bagaimana kos pengiraan berskala apabila input semakin besar dan besar. Ini membawa kita untuk mewakili kos algoritma sebagai fungsi panjang input.

Keluarga Circuit

Input kepada masalah pengiraan tertentu boleh berbeza panjang, berpotensi menjadi sewenang-wenangnya besar. Setiap Circuit, sebaliknya, mempunyai bilangan Gate dan wayar yang tetap. Atas sebab ini, apabila kita memikirkan algoritma dalam istilah Circuit, kita umumnya memerlukan keluarga Circuit yang tidak terhingga besar untuk mewakili algoritma. Dengan keluarga Circuit, kita maksudkan urutan Circuit yang berkembang dalam saiz, membolehkan input yang semakin besar diakomodasi.

Sebagai contoh, bayangkan kita mempunyai algoritma klasik untuk pemfaktoran integer, seperti yang digunakan oleh factorint. Seperti semua algoritma klasik, algoritma ini boleh dilaksanakan menggunakan Circuit Boolean — tetapi untuk melakukannya kita memerlukan Circuit yang berasingan untuk setiap panjang input yang mungkin. Jika kita melihat Circuit yang terhasil untuk panjang input yang berbeza, kita akan melihat bahawa saiznya secara semula jadi berkembang seiring dengan pertumbuhan panjang input — mencerminkan hakikat bahawa memfaktorkan integer 4-bit adalah jauh lebih mudah dan memerlukan operasi asas yang jauh lebih sedikit berbanding memfaktorkan integer 1024-bit, misalnya.

Ini membawa kita untuk mewakili kos pengiraan bagi algoritma dengan fungsi $t,$ yang ditakrifkan supaya $t(n)$ adalah bilangan Gate dalam Circuit yang melaksanakan algoritma untuk input $n$ bit. Dalam istilah yang lebih formal, algoritma dalam model Circuit Boolean dihuraikan oleh urutan Circuit $\{C_1, C_2, C_3,\ldots\},$ di mana $C_n$ menyelesaikan masalah yang kita bicarakan untuk input $n$-bit (atau, secara lebih umum, untuk input yang saiznya diparameterkan dalam beberapa cara oleh $n$), dan fungsi $t$ yang mewakili kos algoritma ini ditakrifkan sebagai

$$t(n) = \operatorname{size}(C_n).$$

Untuk Circuit kuantum keadaannya adalah serupa, di mana Circuit yang semakin besar diperlukan untuk mengakomodasi rentetan input yang semakin panjang.

Contoh: penambahan integer

Untuk menjelaskan lebih lanjut, mari luangkan masa untuk mempertimbangkan masalah penambahan integer, yang jauh lebih mudah berbanding pemfaktoran integer atau bahkan mengira GCD.

Penambahan integer

Input: integer $N$ dan $M$
Output: $N+M$

Bagaimana kita boleh mereka bentuk Circuit Boolean untuk menyelesaikan masalah ini?

Untuk memudahkan perkara, mari hadkan perhatian kita kepada kes di mana $N$ dan $M$ kedua-duanya adalah integer bukan negatif yang diwakili oleh rentetan $n$-bit menggunakan notasi binari. Kita akan membenarkan sebarang bilangan sifar pendahulu dalam pengekodan ini, supaya

$$0\leq N,M\leq 2^n - 1.$$

Output akan menjadi rentetan binari $(n+1)$-bit yang mewakili jumlah, yang merupakan bilangan bit maksimum yang kita perlukan untuk menyatakan hasilnya.

Kita mulakan dengan algoritma — algoritma standard untuk penambahan perwakilan binari — yang merupakan analogi asas $2$ kepada cara penambahan diajar di sekolah rendah di seluruh dunia. Algoritma ini boleh dilaksanakan dengan Circuit Boolean seperti berikut.

Bermula daripada bit paling tidak signifikan, kita boleh mengira XOR mereka untuk menentukan bit paling tidak signifikan bagi jumlah. Kemudian kita mengira bit bawa, yang merupakan AND bagi dua bit paling tidak signifikan daripada $N$ dan $M.$ Kadang-kadang kedua-dua operasi ini bersama dikenali sebagai penambah separuh.

Menggunakan Circuit XOR yang telah kita lihat beberapa kali bersama dengan Gate AND dan dua Gate FANOUT, kita boleh membina penambah separuh dengan 10 Gate. Jika atas sebab tertentu kita berubah fikiran dan memutuskan untuk memasukkan Gate XOR dalam set operasi asas kita, kita akan memerlukan 1 Gate AND, 1 Gate XOR, dan 2 Gate FANOUT untuk membina penambah separuh.

Beralih kepada bit yang lebih signifikan, kita boleh menggunakan prosedur yang serupa, tetapi kali ini memasukkan bit bawa dari setiap kedudukan sebelumnya ke dalam pengiraan kita. Dengan mengalirkan dua penambah separuh dan mengambil OR daripada bit bawa yang dihasilkannya, kita boleh mencipta apa yang dikenali sebagai penambah penuh.

Ini memerlukan 21 Gate secara keseluruhannya: 2 Gate AND, 2 Gate XOR (masing-masing memerlukan 7 Gate untuk dilaksanakan), satu Gate OR, dan 4 Gate FANOUT.

Akhirnya, dengan mengalirkan penambah penuh, kita memperoleh Circuit Boolean untuk penambahan integer bukan negatif. Sebagai contoh, Circuit berikut mengira jumlah dua integer 4-bit.

Secara umum, ini memerlukan

$$21 (n-1) + 10 = 21 n - 11$$

Gate. Sekiranya kita memutuskan untuk memasukkan Gate XOR dalam set operasi asas kita, kita akan memerlukan $2n-1$ Gate AND, $2n-1$ Gate XOR, $n-1$ Gate OR, dan $4n-2$ Gate FANOUT, untuk jumlah $9n-5$ Gate. Jika tambahan pula kita memutuskan untuk tidak mengira Gate FANOUT, jumlahnya ialah $5n-3$ Gate.

Notasi asimptotik

Di satu pihak, memang bagus untuk tahu dengan tepat berapa banyak get yang diperlukan untuk melaksanakan pelbagai pengiraan, seperti dalam contoh penambahan integer di atas. Butiran ini penting untuk benar-benar membina litar.

Di pihak lain, kalau kita buat analisis pada tahap butiran ini untuk semua pengiraan yang kita minati, termasuk yang jauh lebih rumit daripada penambahan, kita akan cepat tenggelam dalam butiran. Untuk memastikan perkara mudah diurus, dan untuk sengaja mengetepikan butiran yang kurang penting, kita biasanya menggunakan notasi Big-O semasa menganalisis algoritma. Melalui notasi ini kita boleh menyatakan tertib pertumbuhan fungsi.

Secara formal, jika kita ada dua fungsi $g(n)$ dan $h(n),$ kita tulis bahawa $g(n) = O(h(n))$ jika wujud nombor nyata positif $c > 0$ dan integer positif $n_0$ sedemikian hingga

$$g(n) \leq c\cdot h(n)$$

untuk semua $n \geq n_0.$ Biasanya $h(n)$ dipilih sebagai ungkapan yang sesederhana mungkin, supaya notasi boleh digunakan untuk mendedahkan kelakuan had sesuatu fungsi dalam istilah mudah. Contohnya, $17 n^3 - 257 n^2 + 65537 = O(n^3).$

Notasi ini boleh dilanjutkan kepada fungsi yang mempunyai beberapa argumen dengan cara yang agak mudah. Sebagai contoh, jika kita ada dua fungsi $g(n,m)$ dan $h(n,m)$ yang ditakrifkan pada integer positif $n$ dan $m,$ kita tulis bahawa $g(n,m) = O(h(n,m))$ jika wujud nombor nyata positif $c > 0$ dan integer positif $k_0$ sedemikian hingga

$$g(n,m) \leq c\cdot h(n,m)$$

apabila $n+m \geq k_0.$

Mengaitkan notasi ini dengan contoh penambahan integer bukan negatif, kita simpulkan bahawa wujud keluarga litar Boolean $\{C_1, C_2,\ldots,\},$ di mana $C_n$ menjumlahkan dua integer bukan negatif $n$-bit bersama, sedemikian hingga $\operatorname{size}(C_n) = O(n).$ Ini mendedahkan ciri paling penting tentang cara kos penambahan skala dengan saiz input: ia skala secara linear.

Perhatikan juga bahawa ia tidak bergantung pada butiran khusus sama ada kita menganggap get XOR mempunyai kos satu unit atau kos $7.$ Secara umum, menggunakan notasi Big-O membolehkan kita membuat pernyataan tentang kos pengiraan yang tidak sensitif terhadap butiran peringkat rendah sedemikian.

Lebih banyak contoh

Berikut adalah beberapa contoh lagi masalah daripada teori nombor pengiraan, bermula dengan pendaraban.

Pendaraban integer

Input: integer $N$ dan $M$
Output: $NM$

Membuat litar Boolean untuk masalah ini lebih sukar daripada membuat litar untuk penambahan — tetapi dengan memikirkan algoritma pendaraban standard, kita boleh menghasilkan litar bersaiz $O(n^2)$ untuk masalah ini (dengan andaian $N$ dan $M$ kedua-duanya diwakili oleh perwakilan binari $n$-bit). Secara lebih umum, jika $N$ mempunyai $n$ bit dan $M$ mempunyai $m$ bit, terdapat litar Boolean bersaiz $O(nm)$ untuk mendarabkan $N$ dan $M.$

Sebenarnya ada cara lain untuk membiak yang berskala lebih baik. Sebagai contoh, algoritma pendaraban Schönhage-Strassen boleh digunakan untuk membuat litar Boolean bagi mendarabkan dua integer $n$-bit pada kos $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n))).$ Walau bagaimanapun, kerumitan kaedah ini menyebabkan banyak overhed, menjadikannya hanya praktikal untuk nombor yang mempunyai puluhan ribu bit.

Masalah asas lain ialah pembahagian, yang kita tafsirkan bermaksud mengira kedua-dua hasil bagi dan baki dengan diberi pembahagi dan dividen integer.

Pembahagian integer

Input: integer $N$ dan $M\neq0$
Output: integer $q$ dan $r$ yang memenuhi $0\leq r < |M|$ dan $N = q M + r$

Kos pembahagian integer adalah serupa dengan pendaraban: jika $N$ mempunyai $n$ bit dan $M$ mempunyai $m$ bit, terdapat litar Boolean bersaiz $O(nm)$ untuk menyelesaikan masalah ini. Dan seperti pendaraban, kaedah yang lebih unggul secara asimptotik adalah diketahui.

Kita kini boleh membandingkan algoritma yang diketahui untuk mengira GCD dengan algoritma untuk penambahan dan pendaraban. Algoritma Euclid untuk mengira GCD bagi nombor $n$-bit $N$ dan nombor $m$-bit $M$ memerlukan litar Boolean bersaiz $O(nm),$ serupa dengan algoritma standard untuk pendaraban dan pembahagian. Juga serupa dengan pendaraban dan pembahagian, terdapat algoritma GCD yang lebih pantas secara asimptotik — termasuk yang memerlukan $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$ operasi asas untuk mengira GCD dua nombor $n$-bit.

Satu pengiraan yang agak lebih mahal yang timbul dalam teori nombor ialah pempangkatan modular.

Pempangkatan modular integer

Input: integer $N,$ $K,$ dan $M$ dengan $K\geq 0$ dan $M\geq 1$
Output: $N^K \hspace{1mm} (\text{mod }M)$

Dengan $N^K\hspace{1mm} (\text{mod }M)$ kita maksudkan baki apabila $N^K$ dibahagikan dengan $M,$ bermaksud integer unik $r$ yang memenuhi $0\leq r < M$ dan $N^K = q M + r$ untuk suatu integer $q.$

Jika $N$ mempunyai $n$ bit, $M$ mempunyai $m$ bit, dan $K$ mempunyai $k$ bit, masalah ini boleh diselesaikan oleh litar Boolean bersaiz $O(k m^2 + nm).$ Ini sama sekali tidak jelas. Penyelesaiannya bukan dengan mengira $N^K$ dahulu kemudian mengambil baki, yang akan memerlukan penggunaan bit yang terlampau banyak hanya untuk menyimpan nombor $N^K.$ Sebaliknya, kita boleh menggunakan algoritma kuasa (yang dikenali juga sebagai kaedah binari dan kuasa dua berulang), yang menggunakan perwakilan binari $K$ untuk melaksanakan seluruh pengiraan modulo $M.$ Dengan andaian $N,$ $M,$ dan $K$ semuanya nombor $n$-bit, kita memperoleh algoritma $O(n^3)$ — atau algoritma masa kubik. Dan sekali lagi, terdapat algoritma yang diketahui lebih rumit tetapi lebih pantas secara asimptotik.

Kos pemfaktoran integer

Berbeza dengan algoritma yang baru dibincangkan, algoritma yang diketahui untuk pemfaktoran integer jauh lebih mahal — seperti yang kita jangka daripada perbincangan awal pelajaran ini.

Satu pendekatan mudah untuk memfaktor ialah pembahagian percubaan, di mana algoritma mencari melalui senarai $2,\ldots,\sqrt{N}$ untuk mencari faktor perdana bagi nombor input $N.$ Ini memerlukan $O(2^{n/2})$ ulangan dalam kes terburuk apabila $N$ adalah nombor $n$-bit. Setiap ulangan memerlukan pembahagian percubaan, bermakna $O(n^2)$ operasi asas untuk setiap ulangan (menggunakan algoritma standard untuk pembahagian integer). Kita akhirnya mendapat litar bersaiz $O(n^2 2^{n/2}),$ yang bersifat eksponen dalam saiz input $n.$

Terdapat algoritma untuk pemfaktoran integer yang mempunyai skala lebih baik. Saringan medan nombor yang disebutkan sebelumnya, contohnya, yang merupakan algoritma yang menggunakan rawak, secara amnya dipercayai (tetapi tidak dibuktikan secara ketat) memerlukan

$$2^{O(n^{1/3} (\operatorname{lg}(n))^{2/3})}$$

operasi asas untuk memfaktor integer $n$-bit dengan kebarangkalian tinggi. Walaupun ia sangat ketara bahawa $n$ dipangkatkan kepada kuasa $1/3$ dalam eksponen ungkapan ini, hakikat ia muncul dalam eksponen masih menjadi masalah yang menyebabkan skala yang buruk — dan menjelaskan sebahagiannya mengapa RSA1024 masih berada di luar domain kebolehterapannya.

Kos polinomial berbanding eksponen

Algoritma klasik untuk penambahan integer, pendaraban, pembahagian, dan pengiraan pembahagi sepunya terbesar membolehkan kita menyelesaikan masalah ini dalam sekelip mata untuk input dengan ribuan bit. Penambahan mempunyai kos linear manakala tiga masalah lain mempunyai kos kuadratik (atau kos subkuadratik menggunakan algoritma pantas secara asimptotik). Pempangkatan modular lebih mahal tetapi masih boleh dilakukan dengan agak cekap, dengan kos kubik (atau kos sub-kubik menggunakan algoritma pantas secara asimptotik).

Kesemua ini adalah contoh algoritma yang mempunyai kos polinomial, bermakna ia mempunyai kos $O(n^c)$ untuk sesetengah pilihan pemalar tetap $c > 0.$ Sebagai anggaran kasar dan peringkat pertama, algoritma yang mempunyai kos polinomial secara abstrak dilihat sebagai mewakili algoritma yang cekap.

Sebaliknya, algoritma klasik yang diketahui untuk pemfaktoran integer mempunyai kos eksponen. Kadang-kadang kos saringan medan nombor digambarkan sebagai sub-eksponen kerana $n$ dipangkatkan kepada kuasa $1/3$ dalam eksponen, tetapi dalam teori kerumitan adalah lebih biasa untuk menempah istilah ini bagi algoritma yang kosnya ialah

$$O\bigl(2^{n^{\varepsilon}}\bigr)$$

untuk setiap $\varepsilon > 0.$ Masalah yang dipanggil NP-lengkap adalah kelas masalah yang tidak diketahui (dan secara meluas diteorikan tidak) mempunyai algoritma kos polinomial. Satu formulasi berasaskan litar bagi hipotesis masa eksponen mengandaikan sesuatu yang lebih kuat lagi, iaitu tiada masalah NP-lengkap boleh mempunyai algoritma kos sub-eksponen.

Kaitan algoritma kos polinomial dengan algoritma cekap mestilah difahami sebagai satu abstraksi yang longgar. Tentu saja, jika kos sesuatu algoritma skala sebagai $n^{1000}$ atau $n^{1000000}$ untuk input bersaiz $n,$ maka agak berlebihan untuk menggambarkan algoritma itu sebagai cekap. Walau bagaimanapun, walaupun algoritma yang mempunyai kos yang skala sebagai $n^{1000000}$ pasti melakukan sesuatu yang bijak untuk mengelakkan kos eksponen, yang secara umumnya kita jangkakan daripada algoritma yang berdasarkan "daya kasar" atau "carian menyeluruh." Malah penghalusan canggih saringan medan nombor, contohnya, gagal mengelakkan skala eksponen dalam kos ini. Algoritma kos polinomial, sebaliknya, berjaya mengambil kesempatan daripada struktur masalah dengan cara tertentu yang mengelakkan skala eksponen.

Dalam praktiknya, pengenalpastian algoritma kos polinomial untuk sesuatu masalah hanyalah langkah pertama menuju kecekapan sebenar. Melalui penghalusan algoritma, algoritma kos polinomial dengan eksponen besar kadang-kadang boleh diperbaiki secara dramatik, menurunkan kos kepada skala polinomial yang lebih "munasabah". Kadang-kadang perkara menjadi lebih mudah apabila ia diketahui boleh dilakukan — jadi pengenalpastian algoritma kos polinomial untuk sesuatu masalah juga boleh memberi kesan menginspirasi algoritma baru yang lebih cekap lagi.

Apabila kita mempertimbangkan kelebihan pengkomputeran kuantum berbanding pengkomputeran klasik, pandangan kita biasanya diarahkan pertama sekali kepada kelebihan eksponen, atau sekurang-kurangnya kelebihan super-polinomial — idealnya mencari algoritma kuantum kos polinomial untuk masalah yang tidak diketahui mempunyai algoritma klasik kos polinomial. Kelebihan teoritikal pada peringkat ini mempunyai peluang terbesar untuk membawa kepada kelebihan praktikal sebenar — tetapi mengenal pasti kelebihan sedemikian adalah cabaran yang amat sukar. Hanya beberapa contoh yang diketahui pada masa ini, tetapi pencarian terus berlanjutan.

Kelebihan polinomial (tetapi bukan super-polinomial) dalam kos pengiraan kuantum berbanding klasik juga menarik dan tidak sepatutnya diabaikan — tetapi memandangkan jurang semasa antara teknologi pengkomputeran kuantum dan klasik, ia memang kelihatan agak kurang menarik pada masa ini. Namun suatu hari nanti, ia mungkin menjadi penting. Algoritma Grover, contohnya, yang dibahas dalam pelajaran kemudian, menawarkan kelebihan kuadratik kuantum berbanding klasik untuk apa yang dipanggil carian tidak berstruktur, dan mempunyai potensi untuk aplikasi yang luas.

Kos tersembunyi pengiraan litar

Terdapat satu isu terakhir yang patut disebutkan, walaupun kita tidak akan membimbangkan diri kita tentangnya lagi dalam kursus ini. Terdapat kos pengiraan "tersembunyi" apabila kita bekerja dengan litar, dan ia berkaitan dengan spesifikasi litar itu sendiri. Apabila input semakin panjang, litar yang semakin besar diperlukan — tetapi kita perlu mendapatkan penerangan litar ini entah bagaimana jika kita hendak melaksanakannya.

Untuk semua contoh yang telah kita bincangkan, atau yang akan dibincangkan dalam pelajaran seterusnya, terdapat algoritma asas dari mana litar diterbitkan. Biasanya litar dalam sesebuah keluarga mengikut beberapa corak asas yang mudah untuk diekstrapolasi kepada input yang semakin besar, seperti menggabungkan penjumlah penuh untuk membuat litar Boolean untuk penambahan atau melakukan lapisan get Hadamard dan get lain dalam beberapa corak yang mudah diterangkan.

Tetapi apa yang berlaku jika terdapat kos pengiraan yang menghalang yang berkaitan dengan corak dalam litar itu sendiri? Sebagai contoh, penerangan setiap ahli $C_n$ dalam keluarga litar boleh, pada dasarnya, ditentukan oleh beberapa fungsi $n$ yang amat sukar dikira.

Jawapannya ialah ini memang satu masalah — dan oleh itu kita mesti meletakkan sekatan tambahan pada keluarga litar selain daripada mempunyai kos polinomial agar ia benar-benar mewakili algoritma yang cekap. Sifat keseragaman untuk litar melakukan ini dengan menetapkan bahawa, dalam pelbagai formulasi tepat, ia mestilah mudah dari segi pengiraan untuk mendapatkan penerangan setiap litar dalam keluarga. Semua keluarga litar yang akan kita bincangkan memang mempunyai sifat ini — tetapi ini adalah isu penting yang perlu disedari secara umum apabila mengkaji model litar pengiraan dari sudut pandang formal.