Pengenalan Algoritma Kerumitan Masa

Dalam sains komputer, analisis algoritma adalah bahagian yang sangat penting. Penting untuk mencari algoritma yang paling berkesan untuk menyelesaikan masalah. Mungkin ada banyak algoritma untuk menyelesaikan masalah, tetapi cabarannya adalah memilih yang paling efisien.

Sekarang intinya adalah, bagaimana kita dapat mengenali algoritma yang paling efisien jika kita mempunyai satu set algoritma yang berbeza? Di sini, konsep algoritma kerumitan ruang dan masa wujud. Kerumitan ruang dan masa bertindak sebagai skala pengukuran untuk algoritma. Kami membandingkan algoritma berdasarkan ruang mereka (jumlah memori) dan kerumitan masa (bilangan operasi).

Jumlah memori komputer yang digunakan oleh algoritma ketika dijalankan adalah kerumitan ruang algoritma tersebut. Kami tidak akan membincangkan kerumitan ruang dalam artikel ini (untuk menjadikan artikel ini sedikit lebih kecil).

Kerumitan Masa

Jadi, kerumitan masa adalah bilangan operasi yang dilakukan oleh algoritma untuk menyelesaikan tugasnya (memandangkan setiap operasi memerlukan jumlah masa yang sama). Algoritma yang menjalankan tugas dalam jumlah operasi terkecil dianggap paling efisien dari segi kerumitan masa. Walau bagaimanapun, kerumitan ruang dan waktu juga dipengaruhi oleh faktor seperti sistem operasi dan perkakasan anda, tetapi kami tidak memasukkannya dalam perbincangan ini.

Sekarang untuk memahami kerumitan waktu, kita akan mengambil contoh di mana kita akan membandingkan dua algoritma yang berbeza yang digunakan untuk menyelesaikan masalah tertentu.

Masalahnya adalah mencari. Kita harus mencari elemen dalam array (dalam masalah ini, kita akan menganggap bahawa susunan disusun mengikut urutan menaik). Untuk menyelesaikan masalah ini, kami mempunyai dua algoritma:

1. Carian Linear.

2. Pencarian Perduaan.

Katakan array mengandungi sepuluh elemen, dan kita mesti mencari nombor sepuluh dalam array.

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; const search_digit = 10;

Algoritma carian linear akan membandingkan setiap elemen array dengan search_digit . Apabila mencari search_digit dalam array, ia akan menjadi benar .

Sekarang mari kita hitung jumlah operasi yang dilakukannya. Di sini, jawapannya adalah 10 (kerana membandingkan setiap elemen larik). Oleh itu, carian Linear menggunakan sepuluh operasi untuk mencari elemen yang diberikan (ini adalah jumlah operasi maksimum untuk array ini; dalam kes carian Linear, ini juga dikenali sebagai algoritma terburuk).

Secara umum, carian Linear akan mengambil n beberapa operasi dalam kes paling buruk (di mana n adalah saiz array).

Mari kita periksa algoritma carian Binari untuk kes ini.

Pencarian binari dapat difahami dengan mudah dengan contoh ini:

Sumber: Pelajar

Sekiranya kita cuba menerapkan logik ini pada masalah kita, pertama kita akan membandingkan search_digit dengan elemen tengah array, iaitu 5. Sekarang kerana 5 kurang dari 10, maka kita akan mula mencari search_digit dalam elemen array lebih besar daripada 5, dengan cara yang sama sehingga kita mendapat elemen 10 yang diinginkan.

Sekarang, cuba hitung jumlah operasi yang dilakukan carian binari untuk mencari elemen yang diinginkan. Ia memerlukan lebih kurang empat operasi. Sekarang, ini adalah keadaan terburuk untuk carian binari. Ini menunjukkan bahawa terdapat hubungan logaritma antara jumlah operasi yang dilakukan dan jumlah ukuran array.

bilangan operasi = log (10) = 4 (lebih kurang)

untuk asas 2

Kami dapat menggeneralisasikan hasil ini untuk carian Binari sebagai:

Untuk susunan ukuran n , bilangan operasi yang dilakukan oleh Binary Search adalah: log (n)

Notasi Big O

Dalam pernyataan di atas, kami melihat bahawa untuk susunan ukuran n , carian linear akan melakukan operasi n untuk menyelesaikan carian. Sebaliknya, carian Binari melakukan log (n) bilangan operasi (kedua-duanya adalah untuk kes terburuk). Kita dapat menggambarkannya sebagai grafik ( paksi-x : bilangan elemen, paksi-y : bilangan operasi).

Sumber: Techtud

Cukup jelas dari angka bahawa kadar peningkatan kerumitan untuk carian Linear jauh lebih pantas daripada carian binari.

Apabila kita menganalisis algoritma, kita menggunakan notasi untuk mewakili kerumitan waktunya dan notasi itu adalah notasi Big O.

Sebagai Contoh: kerumitan masa untuk carian Linear dapat ditunjukkan sebagai O (n) dan O (log n) untuk carian Binari (di mana, n dan log (n) adalah bilangan operasi).

Kerumitan Masa atau notasi Big O untuk beberapa algoritma popular disenaraikan di bawah:

  1. Carian Perduaan: O (log n)
  2. Carian Linear: O (n)
  3. Susun Pantas: O (n * log n)
  4. Susun Pilihan: O (n * n)
  5. Jurujual perjalanan: O (n!)

Kesimpulannya

Saya sangat menghargai usaha anda sekiranya anda masih membaca artikel ini. Sekarang, anda mesti berfikir - mengapa kerumitan masa sangat penting untuk difahami?

Kita tahu bahawa untuk sebilangan kecil elemen (katakanlah 10), perbezaan antara jumlah operasi yang dilakukan oleh carian binari dan carian linear tidak begitu besar. Tetapi di dunia nyata, selalunya, kita menghadapi masalah yang mempunyai banyak data.

Sebagai contoh, jika kita mempunyai 4 bilion elemen untuk dicari, maka, dalam keadaan terburuk, carian linear akan memerlukan 4 bilion operasi untuk menyelesaikan tugasnya. Pencarian binari akan menyelesaikan tugas ini hanya dalam 32 operasi. Itu perbezaan yang besar. Sekarang mari kita anggap bahawa jika satu operasi memerlukan 1 ms untuk diselesaikan, maka carian binari hanya memerlukan 32 ms sedangkan carian linier akan memakan waktu 4 miliar ms (itu adalah sekitar 46 hari). Itulah perbezaan yang ketara.

Inilah sebabnya mengapa mengkaji kerumitan masa menjadi penting apabila terdapat sejumlah besar data.

Sumber

Algoritma Grokking- oleh Aditya Y Bhargava

Pengenalan notasi Big O dan Kerumitan Masa- oleh CS Dojo