Idea analisis algoritma

Rangka Kerja Analisis

1 Gunakan skala input algoritma n sebagai parameter untuk menganalisis kecekapan algoritma

2 Kerumitan masa: Cari operasi asas O(1), dan kemudian hitung bilangan kali ia berjalan (abaikan pemalar pendaraban dan hanya fokus pada bilangan peningkatan)

.

3. Bilangan peningkatan: log2n

4 Kecekapan paling teruk, purata dan terbaik semuanya merujuk kepada kecekapan apabila saiz input ialah n (kecekapan purata boleh diperolehi daripada keputusan yang diketahui)

.

Rangka kerja analisis ringkasan utama:

1 Kecekapan masa dan kecekapan ruang algoritma diukur sebagai fungsi saiz input.

2 Gunakan bilangan pelaksanaan operasi asas algoritma untuk mengukur kecekapan masa, dan gunakan bilangan unit tambahan yang digunakan oleh algoritma untuk mengukur unit ruang

.

3. Apabila skala input adalah sama, kecekapan algoritma bertulis akan berbeza dengan ketara untuk jenis algoritma ini, kecekapan yang paling teruk, purata dan terbaik perlu dianalisis

4 Kebimbangan utama rangka kerja ialah: kecekapannya apabila skala input cenderung tidak terhingga

Notasi asimptotik dan jenis kecekapan asas

1. O(g(n)) ialah set fungsi dengan masa pertumbuhan 2 Ω(g(n)) ialah set fungsi dengan masa pertumbuhan >= c*g(n), tertib lebih rendah

3 θ(g(n)) ialah set fungsi dengan masa pertumbuhan = c*g(n), daripada susunan yang sama

Anda boleh menggunakan had untuk membandingkan bilangan kenaikan (hukum Lópida)

Kecekapan keseluruhan algoritma ditentukan oleh bahagian dengan masa pertumbuhan yang lebih besar.

Skema am untuk analisis matematik masalah bukan rekursif

1. Tentukan parameter yang mewakili metrik saiz input

2 Ketahui operasi asas algoritma

3. Semak sama ada bilangan pelaksanaan operasi asas hanya bergantung pada saiz input Jika ia juga bergantung pada beberapa ciri lain (contohnya: kedudukan elemen dalam tatasusunan, dsb.), analisis yang paling teruk, purata dan. kecekapan terbaik

4. Wujudkan ungkapan penjumlahan (mungkin ungkapan rekursif) bilangan masa pelaksanaan operasi asas algoritma

5 Gunakan operasi standard atau peraturan operasi penjumlahan untuk mewujudkan formula tertutup untuk bilangan operasi, atau sekurang-kurangnya menentukan bilangan peningkatannya

.

Skema am untuk analisis matematik masalah rekursif

1. Tentukan parameter yang mewakili metrik saiz input

2 Ketahui operasi asas algoritma

3. Semak sama ada bilangan pelaksanaan operasi asas hanya bergantung pada saiz input Jika ia juga bergantung pada beberapa ciri lain (contohnya: kedudukan elemen dalam tatasusunan, dsb.), analisis yang paling teruk, purata dan. kecekapan terbaik

4. Untuk bilangan masa pelaksanaan operasi asas algoritma, wujudkan hubungan rekursi dan keadaan awal yang sepadan.

5 Selesaikan pengulangan ini, atau sekurang-kurangnya tentukan bilangan kenaikannya.

Atas ialah kandungan terperinci Idea analisis algoritma. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!