Membangunkan Algoritma Cekap - Mengukur Kecekapan Algoritma Menggunakan Notasi O Besar

Reka bentuk algoritma adalah untuk membangunkan proses matematik untuk menyelesaikan masalah. Analisis algoritma adalah untuk meramal prestasi algoritma. Dua bab sebelumnya memperkenalkan struktur data klasik (senarai, tindanan, baris gilir, baris gilir keutamaan, set dan peta) dan menggunakannya untuk menyelesaikan masalah. Bab ini akan menggunakan pelbagai contoh untuk memperkenalkan teknik algoritma biasa (pengaturcaraan dinamik, bahagi-dan-takluk dan penjejakan ke belakang) untuk membangunkan algoritma yang cekap.

Notasi Big O memperoleh fungsi untuk mengukur kerumitan masa algoritma berdasarkan saiz input. Anda boleh mengabaikan pemalar darab dan istilah tidak mendominasi dalam fungsi. Katakan dua algoritma melakukan tugas yang sama, seperti carian (carian linear vs. carian binari). Mana satu lebih baik? Untuk menjawab soalan ini, anda mungkin melaksanakan algoritma ini dan menjalankan program untuk mendapatkan masa pelaksanaan. Tetapi terdapat dua masalah dengan pendekatan ini:

• Pertama, banyak tugasan dijalankan serentak pada komputer. Masa pelaksanaan program tertentu bergantung pada beban sistem.
• Kedua, masa pelaksanaan bergantung pada input tertentu. Pertimbangkan, sebagai contoh, carian linear dan carian binari. Jika elemen yang akan dicari menjadi yang pertama dalam senarai, carian linear akan menemui elemen itu lebih cepat daripada carian binari.

Sangat sukar untuk membandingkan algoritma dengan mengukur masa pelaksanaannya. Untuk mengatasi masalah ini, pendekatan teori telah dibangunkan untuk menganalisis algoritma bebas daripada komputer dan input khusus. Pendekatan ini menghampiri kesan perubahan pada saiz input. Dengan cara ini, anda boleh melihat seberapa pantas masa pelaksanaan algoritma meningkat apabila saiz input meningkat, jadi anda boleh membandingkan dua algoritma dengan memeriksa kadar pertumbuhan mereka.

Pertimbangkan carian linear. Algoritma carian linear membandingkan kunci dengan elemen dalam tatasusunan secara berurutan sehingga kunci ditemui atau tatasusunan itu habis. Jika kunci tiada dalam tatasusunan, ia memerlukan n perbandingan untuk tatasusunan saiz n. Jika kunci berada dalam tatasusunan, ia memerlukan perbandingan n/2 secara purata. Masa pelaksanaan algoritma adalah berkadar dengan saiz tatasusunan. Jika anda menggandakan saiz tatasusunan, anda akan menjangkakan bilangan perbandingan akan berganda. Algoritma berkembang pada kadar linear. Kadar pertumbuhan mempunyai susunan magnitud n. Para saintis komputer menggunakan notasi Big O untuk mewakili "tertib magnitud." Menggunakan tatatanda ini, kerumitan algoritma carian linear ialah O(n), disebut sebagai "tertib n." Kami memanggil algoritma dengan kerumitan masa O(n) sebagai algoritma linear dan ia mempamerkan kadar pertumbuhan linear.

Untuk saiz input yang sama, masa pelaksanaan algoritma mungkin berbeza-beza, bergantung pada input. Input yang menghasilkan masa pelaksanaan terpendek dipanggil input kes terbaik dan input yang menghasilkan masa pelaksanaan terpanjang ialah input kes terburuk. Analisis kes terbaik dan
analisis kes terburuk adalah untuk menganalisis algoritma untuk input kes terbaik dan input kes terburuk mereka. Analisis kes terbaik dan kes terburuk tidak mewakili, tetapi analisis kes terburuk sangat berguna. Anda boleh yakin bahawa algoritma tidak akan menjadi lebih perlahan daripada kes yang paling teruk.
Analisis kes purata cuba menentukan jumlah purata masa antara semua kemungkinan input yang sama saiz. Analisis kes purata adalah ideal, tetapi sukar untuk dilakukan, kerana untuk banyak masalah sukar untuk menentukan kebarangkalian relatif dan taburan pelbagai contoh input. Analisis kes terburuk lebih mudah dilakukan, jadi analisis biasanya dijalankan untuk kes terburuk.

Algoritma carian linear memerlukan n perbandingan dalam kes terburuk dan n/2 perbandingan dalam kes purata jika anda hampir sentiasa mencari sesuatu yang diketahui ada dalam senarai. Menggunakan tatatanda Big O, kedua-dua kes memerlukan masa O(n). Pemalar darab (1/2) boleh diabaikan. Analisis algoritma tertumpu pada kadar pertumbuhan. Pemalar pendaraban tidak mempunyai kesan ke atas kadar pertumbuhan. Kadar pertumbuhan untuk n/2 atau 100_n_ adalah sama dengan n, seperti yang digambarkan dalam Jadual di bawah, Kadar Pertumbuhan. Oleh itu, O(n) = O(n/2) = O(100n).

Pertimbangkan algoritma untuk mencari nombor maksimum dalam tatasusunan n elemen. Untuk mencari nombor maksimum jika n ialah 2, ia memerlukan satu perbandingan; jika n ialah 3, dua perbandingan. Secara umum, ia memerlukan n - 1 perbandingan untuk mencari nombor maksimum dalam senarai n elemen. Analisis algoritma adalah untuk saiz input yang besar. Jika saiz input kecil, tidak ada kepentingan dalam menganggar kecekapan algoritma. Apabila n bertambah besar, bahagian n dalam ungkapan n - 1 mendominasi kerumitan. Notasi Big O membolehkan anda mengabaikan bahagian tidak mendominasi (cth., -1 dalam
ungkapan n - 1) dan serlahkan bahagian penting (cth., n dalam ungkapan n - 1). Oleh itu, kerumitan algoritma ini ialah O(n).

Notasi Big O menganggarkan masa pelaksanaan algoritma berkaitan dengan saiz input. Jika masa tidak berkaitan dengan saiz input, algoritma dikatakan mengambil masa malar dengan notasi O(1). Contohnya, kaedah yang mendapatkan semula elemen pada indeks tertentu dalam tatasusunan
mengambil masa yang tetap, kerana masa tidak berkembang apabila saiz tatasusunan bertambah.

Penjumlahan matematik berikut selalunya berguna dalam analisis algoritma:

Kerumitan masa ialah ukuran masa pelaksanaan menggunakan tatatanda Big-O. Begitu juga, anda juga boleh mengukur kerumitan ruang menggunakan tatatanda Big-O. Kerumitan ruang mengukur jumlah ruang memori yang digunakan oleh algoritma. Kerumitan ruang untuk kebanyakan algoritma yang dibentangkan dalam buku ialah O(n). iaitu, mereka mengeluarkan kadar pertumbuhan linear kepada saiz input. Contohnya, kerumitan ruang untuk carian linear ialah O(n).

Atas ialah kandungan terperinci Membangunkan Algoritma Cekap - Mengukur Kecekapan Algoritma Menggunakan Notasi O Besar. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!