Asas Teori Kerumitan Pengiraan EITC/IS/CCTF

Oleh kerana jumlah sumber yang diperlukan untuk menjalankan algoritma berbeza dengan saiz input, kerumitan biasanya dinyatakan sebagai fungsi f(n), di mana n ialah saiz input dan f(n) sama ada kerumitan terburuk ( jumlah maksimum sumber yang diperlukan merentas semua input saiz n) atau kerumitan purata kes (purata jumlah sumber ke atas semua input saiz n). Bilangan operasi asas yang diperlukan pada input bersaiz n biasanya dinyatakan sebagai kerumitan masa, di mana operasi asas dipercayai mengambil masa yang tetap pada komputer tertentu dan berubah hanya dengan faktor malar apabila dijalankan pada mesin yang berbeza. Jumlah memori yang diperlukan oleh algoritma pada input saiz n dikenali sebagai kerumitan ruang.

Masa adalah sumber yang paling biasa dianggap. Apabila istilah "kerumitan" digunakan tanpa kelayakan, ia biasanya merujuk kepada kerumitan masa.

Unit masa tradisional (saat, minit, dan seterusnya) tidak digunakan dalam teori kerumitan kerana ia terlalu bergantung pada komputer yang dipilih dan kemajuan teknologi. Sebagai contoh, komputer hari ini boleh melaksanakan algoritma dengan ketara lebih cepat daripada komputer dari tahun 1960-an, namun, ini disebabkan oleh penemuan teknologi dalam perkakasan komputer dan bukannya kualiti algoritma yang wujud. Matlamat teori kerumitan adalah untuk mengukur keperluan masa yang wujud bagi algoritma, atau had masa asas yang akan dikenakan oleh algoritma pada mana-mana komputer. Ini dicapai dengan mengira bilangan operasi asas yang dilakukan semasa pengiraan. Prosedur ini biasanya dirujuk sebagai langkah kerana ia dianggap mengambil masa yang tetap pada mesin tertentu (iaitu, ia tidak terjejas oleh jumlah input).

Satu lagi sumber penting ialah jumlah memori komputer yang diperlukan untuk melaksanakan algoritma.

Satu lagi sumber yang sering digunakan ialah jumlah operasi aritmetik. Dalam senario ini, istilah "kerumitan aritmetik" digunakan. Kerumitan masa secara amnya adalah hasil darab kerumitan aritmetik dengan faktor malar jika kekangan atas saiz perwakilan binari nombor yang berlaku semasa pengiraan diketahui.

Saiz integer yang digunakan semasa pengiraan tidak dikekang untuk banyak kaedah, dan adalah tidak realistik untuk menganggap bahawa operasi aritmetik memerlukan jumlah masa yang tetap. Akibatnya, kerumitan masa, juga dikenali sebagai kerumitan bit, mungkin jauh lebih tinggi daripada kerumitan aritmetik. Kesukaran aritmetik untuk mengira penentu bagi matriks integer nn, sebagai contoh, ialah O(n^3) untuk teknik piawai (penghapusan Gaussian). Oleh kerana saiz pekali mungkin berkembang secara eksponen semasa pengiraan, kerumitan bit kaedah yang sama adalah eksponen dalam n. Jika teknik ini digunakan bersama dengan aritmetik berbilang modular, kerumitan bit boleh dikurangkan kepada O(n^4).

Kerumitan bit, dalam istilah formal, merujuk kepada bilangan operasi pada bit yang diperlukan untuk menjalankan algoritma. Ia menyamai kerumitan temporal sehingga faktor malar dalam kebanyakan paradigma pengiraan. Bilangan operasi pada perkataan mesin yang diperlukan oleh komputer adalah berkadar dengan kerumitan bit. Untuk model pengiraan realistik, kerumitan masa dan kerumitan bit adalah sama.

Sumber yang sering dipertimbangkan dalam menyusun dan mencari ialah jumlah perbandingan entri. Jika data disusun dengan baik, ini adalah penunjuk yang baik tentang kerumitan masa.

Pada semua input yang berpotensi, mengira bilangan langkah dalam algoritma adalah mustahil. Oleh kerana kerumitan input meningkat dengan saiznya, ia biasanya diwakili sebagai fungsi saiz input n (dalam bit), dan oleh itu kerumitan adalah fungsi n. Untuk input bersaiz sama, bagaimanapun, kerumitan algoritma boleh berbeza-beza dengan ketara. Akibatnya, pelbagai fungsi kerumitan digunakan secara rutin.

Kerumitan kes terburuk ialah jumlah semua kerumitan untuk semua saiz n input, manakala kerumitan purata kes ialah jumlah semua kerumitan untuk semua saiz n input (ini masuk akal, kerana bilangan input yang mungkin bagi saiz tertentu adalah terhingga). Apabila istilah "kerumitan" digunakan tanpa ditakrifkan lagi, kerumitan masa kes terburuk diambil kira.

Kerumitan kes terburuk dan kes purata amat sukar untuk dikira dengan betul. Tambahan pula, nilai tepat ini mempunyai sedikit aplikasi praktikal kerana sebarang perubahan dalam mesin atau paradigma pengiraan akan mengubah sedikit kerumitan. Tambahan pula, penggunaan sumber tidak penting untuk nilai n yang kecil, oleh itu kemudahan pelaksanaan selalunya lebih menarik daripada kerumitan rendah untuk n kecil.

Atas sebab ini, kebanyakan perhatian diberikan kepada tingkah laku kerumitan untuk n tinggi, iaitu, tingkah laku asimptotik apabila n menghampiri infiniti. Akibatnya, tatatanda O besar biasanya digunakan untuk menunjukkan kerumitan.

Model pengiraan

Pilihan model pengiraan, yang terdiri daripada menentukan operasi penting yang dilakukan dalam satu unit masa, adalah penting dalam menentukan kerumitan. Ini kadangkala dirujuk sebagai mesin Turing berbilang pita apabila paradigma pengiraan tidak diterangkan secara khusus.

Model pengiraan deterministik ialah model di mana keadaan seterusnya mesin dan operasi yang akan dilakukan ditakrifkan sepenuhnya oleh keadaan sebelumnya. Fungsi rekursif, kalkulus lambda, dan mesin Turing ialah model deterministik pertama. Mesin capaian rawak (juga dikenali sebagai mesin RAM) ialah paradigma popular untuk mensimulasikan komputer dunia sebenar.

Apabila model pengiraan tidak ditakrifkan, mesin Turing berbilang pita biasanya diandaikan. Pada mesin Turing multitape, kerumitan masa adalah sama seperti pada mesin RAM untuk kebanyakan algoritma, walaupun perhatian besar dalam cara data disimpan dalam ingatan mungkin diperlukan untuk mencapai kesetaraan ini.

Pelbagai pilihan boleh dibuat pada beberapa langkah pengiraan dalam model pengkomputeran bukan penentu, seperti mesin Turing bukan penentu. Dalam teori kerumitan, semua pilihan yang boleh dilaksanakan dipertimbangkan pada masa yang sama, dan kerumitan masa bukan penentu ialah jumlah masa yang diperlukan apabila pilihan terbaik sentiasa dibuat. Dengan kata lain, pengiraan dilakukan serentak pada seberapa banyak pemproses (sama) yang diperlukan, dan masa pengiraan bukan deterministik ialah masa yang diambil oleh pemproses pertama untuk menyelesaikan pengiraan. Keselarian ini boleh digunakan dalam pengkomputeran kuantum dengan menggunakan keadaan terjerat terapung apabila menjalankan algoritma kuantum khusus, seperti pemfaktoran Shor bagi integer kecil sebagai contoh.

Walaupun model pengiraan sedemikian tidak boleh dipraktikkan pada masa ini, ia mempunyai kepentingan teori, terutamanya berkaitan dengan masalah P = NP, yang menanyakan sama ada kelas kerumitan yang dihasilkan dengan menggunakan "masa polinomial" dan "masa polinomial bukan deterministik" sebagai sekurang-kurangnya atas. sempadan adalah sama. Pada komputer deterministik, mensimulasikan algoritma NP memerlukan "masa eksponen." Jika tugas boleh diselesaikan dalam masa polinomial pada sistem bukan penentu, ia tergolong dalam kelas kesukaran NP. Jika isu dalam NP dan tidak lebih mudah daripada masalah NP lain, ia dikatakan lengkap NP. Masalah Knapsack, masalah jurujual perjalanan, dan masalah kepuasan Boolean adalah semua masalah gabungan lengkap NP. Algoritma yang paling terkenal mempunyai kerumitan eksponen untuk semua masalah ini. Jika mana-mana isu ini boleh diselesaikan dalam masa polinomial pada mesin penentu, maka semua masalah NP boleh diselesaikan dalam masa polinomial juga, dan P = NP akan ditubuhkan. Sehingga 2017, diandaikan secara meluas bahawa P NP, membayangkan bahawa situasi terburuk masalah NP pada asasnya sukar untuk diselesaikan, iaitu, mengambil masa yang jauh lebih lama daripada mana-mana jangka masa yang boleh dilaksanakan (dekad) memandangkan panjang input yang menarik.

Pengkomputeran selari dan teragih

Pengkomputeran selari dan teragih melibatkan pembahagian pemprosesan merentas berbilang pemproses yang semuanya beroperasi pada masa yang sama. Perbezaan asas antara pelbagai model ialah kaedah menghantar data antara pemproses. Penghantaran data antara pemproses lazimnya sangat cepat dalam pengkomputeran selari, manakala pemindahan data antara pemproses dalam pengkomputeran teragih dilakukan merentasi rangkaian dan dengan itu jauh lebih perlahan.

Pengiraan pada N pemproses mengambil sekurang-kurangnya hasil bagi N daripada masa yang diperlukan pada satu pemproses. Pada hakikatnya, kerana sesetengah subtugas tidak boleh disejajarkan dan sesetengah pemproses mungkin perlu menunggu hasil daripada pemproses lain, batasan ideal secara teori ini tidak akan dapat dicapai.

Isu kerumitan utama adalah untuk membangunkan algoritma supaya produk masa pengkomputeran dengan bilangan pemproses adalah sehampir mungkin dengan masa yang diperlukan untuk melakukan pengiraan yang sama pada satu pemproses.

Pengiraan kuantum

Komputer kuantum ialah komputer dengan model pengiraan berasaskan mekanik kuantum. Tesis Church–Turing berlaku untuk komputer kuantum, membayangkan bahawa sebarang isu yang boleh diselesaikan oleh komputer kuantum juga boleh diselesaikan oleh mesin Turing. Walau bagaimanapun, beberapa tugasan secara teori mungkin diselesaikan menggunakan komputer kuantum dan bukannya komputer klasik dengan kerumitan temporal yang jauh lebih rendah. Buat masa ini, ini hanya teori, kerana tiada siapa yang tahu bagaimana untuk membangunkan komputer kuantum praktikal.

Teori kerumitan kuantum dicipta untuk menyiasat pelbagai jenis isu yang boleh diselesaikan oleh komputer kuantum. Ia digunakan dalam kriptografi pasca-kuantum, iaitu proses mencipta protokol kriptografi yang tahan terhadap serangan komputer kuantum.

Kerumitan masalah (batas bawah)

Kekurangan kerumitan algoritma yang mungkin menyelesaikan masalah, termasuk teknik yang belum ditemui, ialah kerumitan masalah. Akibatnya, kerumitan masalah adalah sama dengan kerumitan mana-mana algoritma yang menyelesaikannya.

Akibatnya, sebarang kerumitan yang diberikan dalam tatatanda O besar mewakili kerumitan kedua-dua algoritma dan masalah yang disertakan.

Sebaliknya, mendapatkan sempadan bawah yang tidak remeh mengenai kerumitan isu selalunya sukar, dan terdapat beberapa strategi untuk melakukannya.

Untuk menyelesaikan kebanyakan isu, semua data input mesti dibaca, yang mengambil masa berkadar dengan magnitud data. Akibatnya, masalah sedemikian mempunyai sekurang-kurangnya kerumitan linear, atau, dalam notasi omega besar, kerumitan Ω(n).

Sesetengah masalah, seperti dalam algebra komputer dan geometri algebra pengiraan, mempunyai penyelesaian yang sangat besar. Kerana output mesti ditulis, kerumitan dikekang oleh saiz maksimum output.

Bilangan perbandingan yang diperlukan untuk algoritma pengisihan mempunyai sempadan bawah tak linear Ω(nlogn). Akibatnya, algoritma pengisihan terbaik adalah yang paling cekap kerana kerumitannya ialah O(nlogn). Hakikat bahawa terdapat n! cara untuk menyusun n perkara membawa kepada batas bawah ini. Kerana setiap perbandingan membahagikan koleksi n! pesanan kepada dua bahagian, bilangan N perbandingan yang diperlukan untuk membezakan semua pesanan mestilah 2N > n!, membayangkan O(nlogn) oleh formula Stirling.

Mengurangkan masalah kepada masalah lain ialah strategi biasa untuk mendapatkan kekangan kerumitan yang dikurangkan.

Pembangunan algoritma

Menilai kerumitan algoritma ialah elemen penting dalam proses reka bentuk kerana ia menyediakan maklumat berguna tentang prestasi yang mungkin dijangkakan.

Ia adalah salah faham yang kerap, akibat daripada undang-undang Moore, yang meramalkan pertumbuhan eksponen kuasa komputer moden, menilai kerumitan algoritma akan menjadi kurang relevan. Ini tidak betul kerana kuasa yang meningkat membolehkan pemprosesan sejumlah besar data (data besar). Sebagai contoh, mana-mana algoritma harus berfungsi dengan baik dalam masa kurang dari satu saat apabila menyusun mengikut abjad senarai beberapa ratus entri, seperti bibliografi buku. Sebaliknya, untuk sejuta penyertaan (contohnya, nombor telefon sebuah bandar besar), algoritma asas yang memerlukan perbandingan O(n2) perlu melakukan satu trilion perbandingan, yang akan mengambil masa tiga jam pada kelajuan 10 juta perbandingan sesaat. Isih cepat dan gabungkan, sebaliknya, hanya memerlukan perbandingan nlogn (sebagai kerumitan purata kes untuk yang pertama, sebagai kerumitan kes terburuk untuk yang terakhir). Ini menghasilkan kira-kira 30,000,000 perbandingan untuk n = 1,000,000, yang akan mengambil masa hanya 3 saat pada 10 juta perbandingan sesaat.

Akibatnya, menilai kerumitan mungkin membenarkan penghapusan banyak algoritma yang tidak cekap sebelum pelaksanaan. Ini juga boleh digunakan untuk memperhalusi algoritma kompleks tanpa perlu menguji semua kemungkinan varian. Kajian kerumitan membolehkan memfokuskan usaha untuk meningkatkan kecekapan pelaksanaan dengan menentukan langkah paling mahal bagi algoritma kompleks.