EITC/IS/CCTF Computational Complexity Theory Fundamentals

Amarga jumlah sumber daya sing dibutuhake kanggo mbukak algoritma beda-beda gumantung karo ukuran input, kerumitan biasane ditulis minangka fungsi f(n), ing ngendi n minangka ukuran input lan f (n) minangka kerumitan paling awon ( jumlah maksimum sumber daya sing dibutuhake ing kabeh input ukuran n) utawa rata-rata kerumitan cilik (rata-rata jumlah sumber daya liwat kabeh input ukuran n). Jumlah operasi dhasar sing dibutuhake ing input ukuran n umume nyatakake minangka kerumitan wektu, ing ngendi operasi dhasar diyakini njupuk wektu sing tetep ing komputer tartamtu lan mung diganti kanthi faktor konstan nalika mbukak ing mesin sing beda. Jumlah memori sing dibutuhake dening algoritma ing input ukuran n dikenal minangka kerumitan spasi.

Wektu minangka sumber daya sing paling umum. Nalika istilah "kerumitan" digunakake tanpa kualifikasi, biasane nuduhake kerumitan wektu.

Unit wektu tradisional (detik, menit, lan liya-liyane) ora digunakake ing teori kompleksitas amarga gumantung banget marang komputer sing dipilih lan kemajuan teknologi. Contone, komputer saiki bisa nglakokake algoritma sing luwih cepet tinimbang komputer wiwit taun 1960-an, nanging iki amarga terobosan teknologi ing hardware komputer tinimbang kualitas algoritma kasebut. Tujuan saka teori kerumitan yaiku kanggo ngitung kabutuhan wektu sing ana ing algoritma, utawa watesan wektu dhasar sing bakal ditindakake dening algoritma ing komputer apa wae. Iki ditindakake kanthi ngitung jumlah operasi dhasar sing ditindakake sajrone komputasi. Prosedur iki umume diarani minangka langkah amarga dianggep mbutuhake wektu sing tetep ing mesin tartamtu (yaiku, ora kena pengaruh jumlah input).

Sumber daya penting liyane yaiku jumlah memori komputer sing dibutuhake kanggo nindakake algoritma.

Sumber daya liyane sing asring digunakake yaiku jumlah operasi aritmetika. Ing skenario iki, istilah "kompleksitas aritmetika" digunakake. Kompleksitas wektu umume minangka asil saka kerumitan aritmetika kanthi faktor konstan yen watesan ndhuwur ing ukuran perwakilan biner saka angka sing kedadeyan sajrone komputasi dikenal.

Ukuran integer sing digunakake sajrone komputasi ora diwatesi kanggo akeh metode, lan ora realistis yen operasi aritmetika mbutuhake wektu sing tetep. Akibaté, kerumitan wektu, uga dikenal minangka kerumitan bit, bisa uga luwih dhuwur tinimbang kerumitan aritmetika. Kesulitan aritmetika kanggo ngitung determinan saka matriks integer nn, contone, yaiku O (n^3) kanggo teknik standar (eliminasi Gaussian). Amarga ukuran koefisien bisa nggedhekake eksponensial sajrone komputasi, kerumitan bit saka cara sing padha eksponensial ing n. Yen teknik kasebut digunakake bebarengan karo aritmetika multi-modular, kerumitan bit bisa dikurangi dadi O(n^4).

Kompleksitas bit, kanthi istilah formal, nuduhake jumlah operasi ing bit sing dibutuhake kanggo mbukak algoritma. Iku padha karo kerumitan temporal nganti faktor konstan ing paling paradigma komputasi. Jumlah operasi ing tembung mesin sing dibutuhake dening komputer sebanding karo kerumitan bit. Kanggo model komputasi sing nyata, kerumitan wektu lan kerumitan bit padha.

Sumber daya sing asring dianggep ing ngurutake lan nggoleki yaiku jumlah entri mbandhingake. Yen data disusun kanthi apik, iki minangka indikator kerumitan wektu sing apik.

Ing kabeh input potensial, ngetung jumlah langkah ing algoritma ora mungkin. Amarga kerumitan input mundhak kanthi ukuran, umume dituduhake minangka fungsi saka ukuran input n (ing bit), lan kerumitan kasebut minangka fungsi n. Nanging, kanggo input ukuran sing padha, kerumitan algoritma bisa beda-beda. Akibaté, macem-macem fungsi kerumitan rutin digunakake.

Kompleksitas kasus paling awon yaiku jumlah kabeh kerumitan kanggo kabeh input ukuran n, dene kerumitan kasus rata-rata yaiku jumlah kabeh kerumitan kanggo kabeh input ukuran n (iki tegese, amarga jumlah input sing mungkin saka ukuran tartamtu yaiku winates). Nalika istilah "kerumitan" digunakake tanpa ditetepake maneh, kerumitan wektu paling awon dianggep.

Kerumitan kasus paling awon lan kasus rata-rata angel banget kanggo ngitung kanthi bener. Salajengipun, angka-angka sing tepat iki ora duwe aplikasi praktis amarga owah-owahan ing mesin utawa paradigma pitungan bakal rada beda karo kerumitan. Salajengipun, panggunaan sumber daya ora penting kanggo nilai cilik n, mula ease saka implementasine asring luwih narik kawigaten saka kerumitan kurang kanggo n cilik.

Kanggo alasan iki, paling manungsa waé mbayar kanggo prilaku kerumitan kanggo n dhuwur, sing, prilaku asimtotik minangka n nyedhaki tanpa wates. Akibaté, notasi O gedhe umume digunakake kanggo nunjukake kerumitan.

Model komputasi

Pilihan model komputasi, sing kalebu nemtokake operasi penting sing ditindakake ing unit wektu, penting kanggo nemtokake kerumitan. Iki kadhangkala diarani minangka mesin Turing multitape nalika paradigma komputasi ora diterangake kanthi spesifik.

Model komputasi deterministik yaiku salah sawijining kahanan mesin lan operasi sing bakal ditindakake kabeh ditemtokake dening negara sadurunge. Fungsi rekursif, kalkulus lambda, lan mesin Turing minangka model deterministik pisanan. Mesin akses acak (uga dikenal minangka RAM-mesin) minangka paradigma populer kanggo simulasi komputer ing donya nyata.

Nalika model komputasi ora ditetepake, mesin Turing multitape biasane dianggep. Ing mesin Turing multitape, kerumitan wektu padha karo mesin RAM kanggo umume algoritma, sanajan ana manungsa waé sing penting babagan cara data disimpen ing memori bisa uga dibutuhake kanggo entuk kesetaraan iki.

Macem-macem pilihan bisa ditindakake ing sawetara langkah komputasi ing model komputasi non-deterministik, kayata mesin Turing non-deterministik. Ing teori kerumitan, kabeh opsi layak dianggep bebarengan, lan kerumitan wektu non-deterministik yaiku jumlah wektu sing dibutuhake nalika pilihan sing paling apik tansah digawe. Kanthi cara liya, komputasi ditindakake bebarengan ing akeh prosesor (padha) kaya sing dibutuhake, lan wektu komputasi non-deterministik yaiku wektu sing ditindakake prosesor pisanan kanggo ngrampungake komputasi. Paralelisme iki bisa digunakake ing komputasi kuantum kanthi nggunakake superposed entangled states nalika nglakokake algoritma kuantum khusus, kayata faktorisasi Shor saka integer cilik, contone.

Sanajan model komputasi kasebut saiki ora bisa ditindakake, nanging nduweni makna teoretis, utamane gegayutan karo masalah P = NP, sing takon yen kelas kerumitan sing diprodhuksi kanthi nggunakake "wektu polinomial" lan "wektu polinomial non-deterministik" minangka paling ndhuwur. watese padha. Ing komputer deterministik, simulasi NP-algoritma mbutuhake "wektu eksponensial." Yen tugas bisa ditanggulangi ing wektu polinomial ing sistem non-deterministik, iku belongs kanggo kelas kangelan NP. Yen masalah ing NP lan ora luwih gampang saka masalah NP liyane, ngandika NP-lengkap. Masalah Knapsack, masalah salesman lelungan, lan masalah kepuasan Boolean kabeh masalah kombinatorial NP-lengkap. Algoritma sing paling kondhang nduweni kerumitan eksponensial kanggo kabeh masalah kasebut. Yen salah siji saka masalah iki bisa ditanggulangi ing wektu polinomial ing mesin deterministik, banjur kabeh masalah NP bisa ditanggulangi ing wektu polinomial uga, lan P = NP bakal ditetepake. Ing taun 2017, umume dianggep yen P NP, tegese kahanan paling awon saka masalah NP pancen angel dirampungake, yaiku, butuh wektu luwih suwe tinimbang wektu sing bisa ditindakake (dasawarsa) sing diwenehi dawa input sing menarik.

Komputasi paralel lan disebarake

Komputasi paralel lan disebarake kalebu proses pamisah ing pirang-pirang pemroses sing kabeh bisa digunakake ing wektu sing padha. Bedane dhasar antarane macem-macem model yaiku cara ngirim data antarane prosesor. Transmisi data ing antarane pemroses biasane cepet banget ing komputasi paralel, dene transfer data antarane pemroses ing komputasi sing disebarake ditindakake ing jaringan lan kanthi mangkono luwih alon.

A pitungan ing N prosesor njupuk paling quotient dening N wektu iku njupuk ing prosesor siji. Ing kasunyatan, amarga sawetara subtugas ora bisa paralel lan sawetara prosesor bisa uga kudu ngenteni asil saka prosesor liyane, iki bound teoritis becik ora bakal digayuh.

Jeksa Agung bisa ngetokake kerumitan tombol mangkono kanggo ngembangaken kalkulus supaya prodhuk wektu komputasi dening nomer prosesor sabisa kanggo wektu sing dibutuhake kanggo nindakake komputasi padha ing prosesor siji.

Komputasi kuantum

Komputer kuantum minangka komputer kanthi model komputasi basis mekanika kuantum. Tesis Church–Turing bener kanggo komputer kuantum, tegese masalah apa wae sing bisa dirampungake dening komputer kuantum bisa uga ditanggulangi dening mesin Turing. Nanging, sawetara tugas bisa sacara teoritis ditanggulangi nggunakake komputer kuantum tinimbang komputer klasik kanthi kerumitan temporal sing luwih murah. Saiki, iki pancen teoritis, amarga ora ana sing ngerti carane ngembangake komputer kuantum praktis.

Teori kompleksitas kuantum digawe kanggo nyelidiki macem-macem jinis masalah sing bisa ditanggulangi dening komputer kuantum. Iki digunakake ing kriptografi pasca-kuantum, yaiku proses nggawe protokol kriptografi sing tahan kanggo serangan komputer kuantum.

Kompleksitas masalah (wates ngisor)

Infimum saka kerumitan algoritma sing bisa ngatasi masalah, kalebu teknik sing durung ditemokake, yaiku kerumitan masalah kasebut. Akibaté, kerumitan masalah padha karo kerumitan algoritma sing bisa ngrampungake.

Akibaté, kerumitan apa wae sing diwenehake ing notasi O gedhe nggambarake kerumitan algoritma lan masalah sing ana.

Ing tangan liyane, nggayuh wates ngisor nontrivial ing kerumitan masalah asring angel, lan ana sawetara Sastranegara kanggo nglakoni.

Kanggo ngatasi masalah paling akeh, kabeh data input kudu diwaca, sing mbutuhake wektu sing cocog karo gedhene data kasebut. Akibaté, masalah kasebut paling ora duwe kompleksitas linier, utawa, ing notasi omega gedhe, kompleksitas Ω(n).

Sawetara masalah, kayata ing aljabar komputer lan geometri aljabar komputasi, duwe solusi sing gedhe banget. Amarga output kudu ditulis, kerumitan diwatesi dening ukuran maksimum output.

Jumlah bandhing sing dibutuhake kanggo algoritma pangurutan nduweni wates ngisor nonlinear Ω(nlogn). Akibaté, algoritma ngurutake paling apik sing paling efisien amarga kerumitan kasebut yaiku O(nlogn). Kasunyatan sing ana n! cara kanggo ngatur n iku ndadékaké kanggo wates ngisor iki. Amarga saben comparison dibagi koleksi iki n! pesenan dadi rong bagéyan, nomer N mbandhingaké dibutuhake kanggo mbedakake kabeh pesenan kudu 2N > n!, implying O(nlogn) dening rumus Stirling.

Ngurangi masalah menyang masalah liyane minangka strategi umum kanggo entuk kendala kerumitan sing suda.

Pangembangan algoritma

Evaluasi kerumitan algoritma minangka unsur penting ing proses desain amarga menehi informasi migunani babagan kinerja sing bisa diarepake.

Iki minangka salah pangerten sing asring, minangka asil saka hukum Moore, sing prédhiksi pertumbuhan eksponensial daya komputer modern, ngevaluasi kerumitan algoritma bakal dadi kurang relevan. Iki ora bener amarga tambah daya ngidini pangolahan data sing akeh banget (data gedhe). Contone, algoritma apa wae kudu bisa dianggo kanthi apik sajrone kurang saka detik nalika ngurutake dhaptar sawetara atusan entri miturut abjad, kayata bibliografi buku. Ing tangan liyane, kanggo yuta entri (contone, nomer telpon kutha gedhe), algoritma dhasar sing mbutuhake O(n2) mbandhingaké kudu nindakake triliun mbandhingaké, kang bakal njupuk telung jam ing kacepetan 10. yuta bandingaken per detik. Quicksort lan nggabung, ing tangan liyane, mung mbutuhake nlogn bandingaken (minangka kerumitan rata-rata cilik kanggo mantan, minangka kerumitan paling awon kanggo terakhir). Iki ngasilake udakara 30,000,000 mbandhingake kanggo n = 1,000,000, sing mung butuh 3 detik kanthi 10 yuta perbandingan per detik.

Akibaté, pambiji kerumitan bisa ngidini kanggo ngilangi akeh algoritma sing ora efisien sadurunge implementasine. Iki uga bisa digunakake kanggo nyempurnakake algoritma kompleks tanpa kudu nyoba kabeh varian sing bisa ditindakake. Sinau babagan kerumitan ngidini fokus upaya kanggo nambah efisiensi implementasine kanthi nemtokake langkah-langkah sing paling larang saka algoritma kompleks.