Kerumitan masa algoritma

Sebagai pengaturcara atau pemaju web, anda mungkin telah membuat algoritma untuk pelbagai tugas - mencari data, susunan penyortiran, laluan, dan lain -lain. Ketepatan adalah yang paling penting - memastikan ia berfungsi seperti yang diharapkan untuk semua input (topik di luar perbincangan ini). Kecekapan adalah sama pentingnya: Bagaimana skala masa pengiraan dengan saiz input? Artikel ini meneroka kerumitan masa, aspek utama kecekapan algoritma.

Takeaways utama:

Big O Notation mengukur hubungan antara runtime algoritma dan saiz input. Ia amat relevan untuk tugas -tugas intensif yang komputasi seperti menyusun dan mengulangi.

Algoritma yang cekap mempunyai kerumitan masa yang lebih rendah, meminimumkan runtime. Carian Perduaan (O (Log N)) mencontohi kecekapan, berbeza dengan algoritma yang tidak cekap seperti Bogosort (O (N*N!)).
Walaupun kerumitan masa adalah penting, ia bukan satu -satunya penentu pilihan algoritma. Keperluan khusus aplikasi, saiz data input, dan sumber yang tersedia juga memainkan peranan penting.
kerumitan masa:

Kerumitan masa menerangkan hubungan antara saiz runtime dan input (selalunya saiz struktur array atau data). Ia kurang relevan untuk operasi mudah (pangkalan data mengambil, penyambungan rentetan) di mana perbezaan runtime boleh diabaikan. Walau bagaimanapun, untuk menyusun, rekursi, dan lain -lain proses pengiraan yang intensif, mengoptimumkan kerumitan masa memberi kesan kepada prestasi. Big O Notation menyediakan cara yang standard untuk menyatakan hubungan ini.

notasi besar:

notasi besar secara matematik mewakili terikat atas faktor skala algoritma. Sebagai contoh, jika menggandakan input berganda runtime, kerumitan adalah O (n) (linear). Mari kita ilustrasikan:

Ini mempunyai kerumitan O (n) kerana skala runtime secara linear dengan saiz array (n). Sekarang pertimbangkan gelung bersarang:

$numbers = array(14,82,4,0,24,28);
foreach($numbers as $number) {
    echo $number;
}

di sini, kerumitan adalah o (n²), kerana gelung dalaman melaksanakan n kali untuk setiap lelaran gelung luar. Big O memberi tumpuan kepada istilah dominan sebagai saiz input pendekatan tak terhingga; O (n² n) memudahkan O (n²).

$numbers = array(14,82,4,0,24,28);
foreach($numbers as $number1) {
    foreach($numbers as $number2) {
        // ... some operation ...
    }
}

Algoritma yang cekap:

Algoritma yang cekap mempamerkan kerumitan masa yang rendah. Carian binari, dengan kerumitan O (log n), adalah contoh utama. Ia berulang kali mengurangkan ruang carian, mencapai carian yang lebih cepat daripada imbasan linear (O (N)).

Algoritma yang tidak cekap:

Sebaliknya, algoritma yang tidak cekap mempunyai kerumitan masa yang tinggi. Bogosort, algoritma penyortiran yang tidak cekap, berulang kali mengepam input sehingga ia disusun. Kerumitan O (n*n!) Menjadikannya tidak praktikal untuk sebarang input bersaiz yang munasabah. Sebaliknya, Heapsort menyediakan penyelesaian yang lebih efisien untuk penyortiran. Reka bentuk dan pengoptimuman algoritma:

mari kita menggambarkan pengoptimuman kerumitan masa. Pertimbangkan fungsi untuk menyusun pelbagai bilangan bulat positif dalam urutan menaik. Jenis penyisipan mudah (O (n²)) mungkin dilaksanakan seperti berikut:

Walaupun berfungsi, O (n²) tidak cekap untuk tatasusunan besar. A Countting Sort (O (N)) menawarkan alternatif yang unggul:

$numbers = array(14,82,4,0,24,28);
foreach($numbers as $number) {
    echo $number;
}

Mengira jenis mencapai kerumitan masa linear dengan memanfaatkan array pengiraan untuk mengesan frekuensi elemen. Walau bagaimanapun, perhatikan bahawa kesesuaian Count Sort bergantung kepada julat nilai input.

$numbers = array(14,82,4,0,24,28);
foreach($numbers as $number1) {
    foreach($numbers as $number2) {
        // ... some operation ...
    }
}

kerumitan masa bukanlah segala -galanya:

Semasa berusaha untuk kecekapan masa adalah penting, ia tidak sepatutnya menjadi tumpuan tunggal. Untuk dataset kecil, perbezaan runtime antara algoritma boleh diabaikan. Selain itu, banyak algoritma yang cekap, yang diuji dengan baik tersedia untuk tugas-tugas biasa seperti menyusun dan mencari.

Soalan -soalan yang sering ditanya (Soalan Lazim):

(Bahagian ini ditinggalkan untuk keringkasan, kerana ia adalah pengulangan pengetahuan umum tentang kerumitan masa.)

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