Miscellaneous

Kompleksitas Waktu: Mengapa Beberapa Algoritma Berjalan Selama Miliaran Tahun

Kompleksitas Waktu: Mengapa Beberapa Algoritma Berjalan Selama Miliaran Tahun

Ini adalah artikel ketiga dalam seri tujuh bagian tentang Algoritma dan Komputasi, yang membahas bagaimana kita menggunakan bilangan biner sederhana untuk menggerakkan dunia kita. Artikel pertama, Bagaimana Algoritma Menjalankan Dunia Tempat Kita Tinggal, dapat ditemukan di sini.

Jika Anda melihat visualisasi dari algoritme pengurutan berbeda yang bekerja pada kumpulan data, akan menjadi sangat jelas, sangat cepat, bahwa beberapa jauh lebih baik daripada yang lain. Dimana satu algoritma mengambil detik untuk menyelesaikannya, yang lain akan mengambil menit bahkan dengan kumpulan data kecil. Untungnya, kami tidak perlu melihat algoritme bekerja untuk mengetahui apakah algoritme tersebut dapat menyelesaikan pekerjaan dengan cepat atau jika algoritme akan runtuh karena bobot inputnya. Itulah apa Notasi Big O adalah untuk, dan sekilas mengetahui apakah file Kompleksitas Waktu algoritme berarti kami akan mendapatkannya dalam beberapa jam atau milyaran tahun.

Apa itu Kompleksitas Waktu?

Dalam istilah yang lebih formal, kompleksitas waktu adalah pengukuran berapa lama suatu algoritme akan diproduksi hasilnya, relatif terhadap ukuran masukannya. Praktis, itu adalah tingkat pertumbuhan dalam jumlah operasi diperlukan untuk menghasilkan hasil untuk setiap unit masukan tambahan.

Dalam artikel pertama dalam seri ini, saya menjelaskan secara langsung algoritma penjumlahan. Untuk menghitung jumlah dari semua nomor antara angka-angka p dan q, Saya mendeklarasikan variabel lain, r, dan setel ke nol. Saya kemudian menambahkan p untuk r, lalu saya menambahkan p + 1 untuk r, kemudian p + 2, dan seterusnya sampai akhirnya saya tambah q sendiri untuk r, pada saat mana saya berhenti dan mengembalikan hasilnya, r, yang menyelenggarakan jumlah.

Berapa banyak operasi yang diperlukan, tanpa mengetahui ukuran input akhir, hanya dengan menggunakan variabel abstrak p dan q? Apa yang sebenarnya kami lakukan adalah menjalankan file loop dimana setiap iterasi meningkat p dengan tepat 1 dan menambahkannya r. Ini sebenarnya adalah tampilan algoritme kami saat disajikan secara lebih formal:

1. biarkan r = 0
2. sementara p adalah <= untuk q
3. r=p+r
4. p = p+1
5. kembali r

Bila ditata seperti inilah yang kita sebut pseudocode, menjadi lebih mudah untuk melihat berapa banyak operasi yang diperlukan. Turunkan nomor langkah demi nomor dan hitung operasi. Yang pertama adalah instruksi, jadi ini adalah operasi tunggal. Baris kedua, bagaimanapun, berbeda. Perulangan seperti ini berulang hingga kondisi terpenuhi, dalam hal ini, sekali p lebih besar dari q. Kami kemudian tahu bahwa kami termasuk q dan p dalam jumlah, jadi banyaknya iterasi melalui ini loop adalah sama dengan q - (p - 1), yang mana ukuran masukan untuk algoritme kami.

Tapi itu hanya berapa kali kita mengulang melalui loop, kita juga harus menghitung operasi di dalamnya, yang mana kita menambahkan p dan r dan menetapkan hasil untuk r dan kemudian kami menambahkan p dan 1 dan kemudian tetapkan hasilnya ke p. Jadi kami tampil dua operasi untuk setiap pengulangan, dan ada q - (p - 1)iterasi. Yang perlu kita lakukan sekarang adalah berkembang biak 2 operasi dan q - (p - 1)iterasi mendapatkan 2 * (q - (p - 1)) operasi untuk seluruh loop. Tambahkan operasi pada 1. dan 5., yang memberi kita hitungan akhir sebesar 2 * (q - (p - 1)) + 2 operasi untuk algoritma ini.

Ini adalah fungsi linier karena tidak ada eksponen, jadi tingkat pertumbuhan untuk algoritma penjumlahan kami adalah langsung terikat ke itu memasukkan ukuran, yang kami sebut kompleksitas waktu linier. Sebagai aturan umum, apapun suku urutan tertinggi dalam rumus yang mendefinisikan kompleksitas waktu kita adalah yang menjadi ciri pertumbuhannya dari waktu ke waktu, jadi kita mengambil suku urutan tertinggi dan membuang sisanya, meninggalkan q - (p - 1), yang akan kita lakukan panggilan n demi kesederhanaan.

Kompleksitas waktu linier mungkin terdengar tidak efisien saat Anda mencitrakan ukuran input dalam miliaran, tetapi waktu linier sebenarnya tidak terlalu buruk. Kami bisa melakukannya dengan lebih baik.

Kami sudah lama mengetahui bahwa jumlah dari semuaangka-angka dari 1 dan q diberikan oleh rumus (q * (q + 1)) / 2. Kami juga tahu bahwa fileproperti komutatif penjumlahan memberi tahu kita bahwa hasil (p-1 * (p)) / 2 dikurangkan dari (q * (q + 1)) / 2 cukup potong bagian dari jumlah yang mencakup segala sesuatu dari 1 untuk p-1, meninggalkan jumlah dari angka-angka dari p untuk q belakang, itulah yang kami inginkan.

Algoritme ini, bergantung pada bagaimana kode itu dikodekan, seharusnya tidak lebih dari tiga operasi. Karena operasi matematika langsung seperti ini persis seperti yang dilakukan komputer lebih baik daripada manusia, kita dapat merangkai rumus menjadi satu ekspresi matematika, dan prosesor akan mengunyahnya semudah jika kita memecahnya menjadi bagian yang lebih kecil, tetapi kami akan tetap berpegang pada tiga operasi untuk saat ini.

1. p = (p-1 * (p)) / 2
2. q
= (q * (q + 1)) / 2
3. kembali ( q -p )

Tidak loop, hanya sejumlah operasi konstan yang tidak berubah, apa pun perbedaannya p dan q adalah. Algoritme ini akan selalu membutuhkan tiga operasi untuk dilakukan, jadi kami menyebutnya kompleksitas waktu yang konstan.

Sekarang, jika Anda tidak tahu apa milik Anda ukuran masukan akan menjadi ketika Anda merancang sebuah algoritma, algoritma mana yang akan Anda gunakan di antara keduanya? Jelas, itu yang ke dua, karena algoritma waktu yang konstan pada dasarnya adalah a makan siang gratis komputasi sejauh menyangkut masukan. Jadi seperti kita meningkatkan program kami untuk menangani lebih banyak data, waktu proses mereka tidak akan banyak berubah, sedangkan kami tahu algoritme pertama kami akan tumbuh persis sebanyak masukan kami, yang bisa bernilai miliaran atau lebih. Tentu saja, kompleksitas waktu yang konstan tidak selalu berarti lebih efisien, tetapi dalam hal ini yang kita inginkan.

Sebelumnya kami pernah duduk untuk menulis baris kode, kami sudah menemukan algoritme yang mana pilihan yang lebih baik untuk masukan kami, dan kami tidak pernah harus menjalankannya untuk mengetahui seberapa baik kerjanya. Inilah mengapa kami menggunakan kompleksitas waktu, hanya saja tidak banyak alat di luar sana yang sama efektifnya menilai efisiensi algoritme.

Apa itu Big O Notation?

Kami memiliki cara khusus untuk menjelaskan efisiensi ini untuk mempermudah, sesuatu yang kami sebut Notasi Big O. Sederhananya, Notasi Big O mewakili algoritmaefisiensi menjalankannya skenario terburuk. Jika Anda harus mencari nama dalam direktori dengan membaca setiap nama sampai Anda menemukan yang benar, skenario terburuknya adalah nama yang Anda inginkan adalah entri terakhir dalam direktori. Ini berarti Anda harus membaca seluruh direktori n nama untuk mendapatkan yang Anda inginkan. Jadi kami katakan algoritma ini adalah O (n), di mana n adalah istilah pesanan tertinggi dalam rumus operasi kami.

Ada lainnya Notasi besar Untuk kasus terbaik dan kasus rata-rata, tapi yang terpenting adalah file skenario terburuk; itulah yang dapat menyebabkan komputer Anda mogok — atau lebih buruk lagi, mobilmu atau pesawat Anda. Mereka langsung menuju ke inti mengapa kompleksitas waktu penting dan tunjukkan mengapa beberapa algoritma tidak bisa menyelesaikan masalah tanpa mengambil beberapa miliar tahun untuk melakukannya.

Jadi bagaimana kita menggunakan Notasi Big O? Bagan di atas menunjukkan kepada Anda bagaimana ini berbeda Notasi Big O lihat dalam praktiknya, dengan sumbu x menjadi masukan Anda dan Anda sumbu y waktu yang dibutuhkan untuk menyelesaikannya. Untuk detail lebih lanjut, Anda akan menemukan daftar cepat dari semua file Notasi Big O yang penting untuk saat ini dan kompleksitas waktu mereka mewakili:

* O (1): Kompleksitas Waktu yang Konstan- Ini adalah free pass komputasi efektif yang telah kita bicarakan sebelumnya. Ini tidak berarti lebih cepat. Itu hanya berarti bahwa kompleksitas waktu tidak terkait dengan ukuran input.

* O (log n): Kompleksitas Waktu Logaritmik- Ini paling umum saat menggunakan file strategi bagi-dan-taklukkan pada kumpulan data, di mana setiap operasi membuang sebagian besar input yang telah dikesampingkan sebagai tidak memiliki solusi. Contoh klasik adalah mencari sebuah kata di kamus: Buka secara acak, periksa bagian huruf Anda, kemudian abaikan bagian di mana Anda tahu kata Anda tidak akan ada, dan secara berulang membagi dan membuang bagian yang tersisa sampai Anda menemukan katamu.

* Di): Kompleksitas Waktu Linear- Ini adalah algoritma penjumlahan kami dari awal.

* O (n log n): Kompleksitas Waktu Linearitmik- Melakukan transformasi Fourier cepat adalah O (n Log n) algoritma, seperti Mergesort a.

* Di2): Kompleksitas Waktu Kuadrat- Ini biasanya ditemukan setiap kali Anda memiliki loop bersarang. Dalam algoritma pertama kita, jika kita memiliki loop kedua dalam yang pertama, fungsinya akan mengembangkan kompleksitas waktu kuadrat.

* Dic, c> 1): Kompleksitas Waktu Polinomial- Kompleksitas Waktu Polinomial adalah sangat penting karena kurang lebih mewakili batas atas tentang apa a komputer klasik dapat menyelesaikannya dalam waktu singkat.

* O (cn, n> 1, c> 1): Kompleksitas Waktu Eksponensial- Di sinilah Anda mulai mendapatkan Algoritme miliaran tahun. Setiap saat a unit masukan menyebabkan Anda menggandakan jumlah operasi yang dilakukan relatif terhadap jumlah yang dilakukan jika masukannyan-1, kamu punya kompleksitas waktu eksponensial. Contoh paling umum yang digunakan kebanyakan orang adalah mencoba menghitung setiap subset yang mungkin dari satu set, tapi Brute-force Sebuah Kunci enkripsi 128-bit biasanya dimasukkan ke dalam kategori ini.

* Di!): Kompleksitas Waktu Faktorial- Ini adalah algoritme yang mungkin dapat berjalan hingga alam semesta mati karena panas jika diberi ukuran input yang cukup besar yaitu beberapa ribu. Kapan pun Anda memiliki sesuatu seperti "berapa banyak cara berbeda yang dapat Anda atur urutan ini," Anda memiliki masalah permutasi dan memaksa cara Anda untuk mendapatkan jawaban membutuhkan pembuatan n! nilai yang berbeda, yang diberikan oleh hasil dari: n * (n - 1) * (n - 2) * ... * 3 * 2 * 1. Ini adalah algoritme yang berjalan hampir paralel dengan sumbu y pada diagram di atas.

Mengapa Kita Tidak Bisa Menghasilkan Algoritma yang Lebih Baik

Ini bukan karena kurang berusaha. Seluruh bidang ilmu komputer teoretis adalah tentang mencoba menemukan yang terbaik algoritma yang efisien untuk masalah tertentu, tapi terkadang kita tidak tahu matematika. Dan bukan hanya Anda dan saya, kita berbicara tentang pemenang Field's Medal yang menghadapi beberapa masalah seperti O (2n) dan Di!) dan tebakan mereka sama bagusnya dengan tebakan kita.

Ada banyak katalog masalah yang belum kita pecahkan matematika — kita akan membahasnya lebih lanjut di akhir seri—, tetapi masalah ini bertindak sebagai titik penghambat yang menciptakan inefisiensi dalam bisnis, penelitian ilmiah, dan lainnya daerah administratif, dan ada banyak orang menunggu masalah ini akhirnya diselesaikan. Hadiah yang sangat menggiurkan bahkan telah ditawarkan kepada siapa saja yang dapat menyelesaikan beberapa dari hal-hal ini tetapi sejauh ini, belum ada yang mampu dan beberapa dari masalah ini telah bertahan selama beberapa dekade.

Alasan mengapa komputer klasik tidak dapat menyelesaikan masalah ini secara efisien, baik dibangun ke dalam sirkuit mesin; setiap instruksi yang diberikan harus diselesaikan sebelum dapat dimulai pada instruksi berikutnya. Sistem multicore atau mesin multiprosesor dapat mempercepat, tetapi Anda mungkin masih membutuhkannya satu atau dua triliun tahun untuk mendapatkan hasil setelah membuang semua prosesor kami dan melepaskannya pada file Di!) masalah dimana n adalah sesuatu seperti 500.

Insinyur komputer telah melihat ini datang selama beberapa dekade, tetapi sekarang kita akhirnya sampai pada garis akhir untuk apa yang dapat kita peras dari komputer klasik. Anda tidak bisa membuatnya operasi berjalan lebih cepat, dan secara alami, mereka bisa hanya melakukan satu operasi dalam satu waktu. Jika Anda memiliki algoritma yang membutuhkan quintillions operasi untuk menyelesaikan, a komputer klasik harus melakukan semua itu operasi dalam rangka. Pada titik itu, waktu yang dibutuhkan untuk mendapatkan hasil hanya tinggal menunggu matematika dan fisika. Jika kita akan memecahkan masalah yang ada ini kompleksitas waktu eksponensial atau lebih besar, kemudian sesuatu yang lain dibutuhkan.

Kabar baiknya adalah kami tahu itu mungkin, di setidaknya satu kasus, untuk menemukan algoritme yang cukup efisien untuk menemukan jawaban dari salah satunya O (2n) masalah di kompleksitas waktu polinomial. Jika bisa dilakukan sekali, maka itu mungkin untuk dilakukan lagi; itu hanya butuh mengesampingkan seluruh hal "fisika".

Artikel keempat dalam seri kami tentang Algoritma dan Komputasi, Bagaimana Algoritma Peter Shor Menghancurkan Enkripsi RSA hingga Gagal, bisa ditemukan disini.


Tonton videonya: Penjelasan Algoritma GREEDY (Desember 2021).