Algoritma & kerumitan: soalan latihan dengan penerangan

Soalan latihan aneka pilihan Algoritma & kerumitan percuma dengan petunjuk dan penerangan, pada tiga tahap: istilah dan fakta utama, menggunakan konsep, kes dan analisis.

Soalan latihan percumaMudah

Kelas kerumitan manakah yang tumbuh paling pantas untuk n yang besar?

Soalan seterusnya →
Berlatih Algoritma & kerumitan secara percumaBerlatih Algoritma & kerumitan sekarang5 soalan percuma setiap hari. Tiada kad diperlukan.

Apa yang anda latih

  1. Mudahistilah dan fakta utama
  2. Sederhanamenggunakan konsep
  3. Sukarkes dan analisis

Pelajari Algoritma & kerumitan dari awal

1Apa yang diukur oleh kerumitan

Algoritma ialah senarai langkah tepat yang terhingga yang menyelesaikan masalah, seperti mengisih senarai atau mencari nama dalam buku telefon.

Dua algoritma boleh menyelesaikan masalah yang sama tetapi mengambil masa yang sangat berbeza. Kerumitan menerangkan bagaimana kerja itu bertambah apabila input menjadi lebih besar.

Saiz input dipanggil n: bilangan item untuk diisih, panjang senarai, bilangan nod dalam graf.

Bayangkan mencari nama dalam buku telefon setebal 1000 halaman. Membaca setiap halaman memerlukan sehingga 1000 langkah. Membukanya di tengah dan membahagi dua setiap kali memerlukan kira-kira 10 langkah.

Kerumitan masa mengira langkah. Kerumitan ruang mengira memori tambahan. Kedua-duanya ditulis sebagai fungsi n.

Biasanya anda melihat kes terburuk: kerja paling banyak bagi semua input bersaiz n. Kadangkala kes purata atau kes terbaik yang diminta.

Semakan kendiri Sebuah algoritma yang kerjanya bertambah seperti n² mengambil 1 saat untuk n = 1000. Kira-kira berapa lama ia mengambil masa untuk n = 2000?
  1. 1 saat
  2. 2 saat
  3. 4 saat
  4. 8 saat

Jawapan: 4 saat. Menggandakan n mendarabkan n² dengan 2² = 4, maka masa naik daripada kira-kira 1 kepada kira-kira 4 saat. 2 saat ialah jawapan bagi pertumbuhan linear, dan 8 bagi n³.

2Big O dan kelas pertumbuhan

Tatatanda Big O hanya mengekalkan perkara yang penting untuk n yang besar. Anda membuang faktor malar dan hanya mengekalkan sebutan yang tumbuh paling pantas.

3n² + 5n + 2 ⇒ O(n²)

Untuk n = 1000 sebutan n² ialah 3 000 000, manakala 5n hanya 5000. Sebutan yang lebih kecil hampir tidak mengubah jumlahnya.

Kelas-kelas ini muncul berulang kali, dari pertumbuhan paling perlahan hingga paling pantas:

  • O(1), malar: membaca elemen tatasusunan melalui indeksnya.
  • O(log n), logaritma: carian binari, yang membahagi dua masalah pada setiap langkah.
  • O(n), linear: satu lintasan merentas semua item, seperti mencari nilai terbesar.
  • O(n log n): algoritma pengisihan yang baik seperti isihan gabung.
  • O(n²), kuadratik: dua gelung bersarang merentas item, seperti isihan gelembung.
  • O(2ⁿ), eksponen: mencuba setiap subset. Ia cepat menjadi tidak boleh digunakan.
ntlog nnn log nn²2ⁿ

Big O ialah batas atas: kerja bertambah paling pantas sebegini. Ω (Big Omega) ialah batas bawah, dan Θ (Theta) ialah batas ketat, kedua-dua atas dan bawah.

Asas logaritma tidak penting dalam Big O, kerana logaritma dengan asas berbeza hanya berbeza dengan faktor malar.

Semakan kendiri Apakah Big O bagi 4n + 2n² + 100?
  1. O(100)
  2. O(2n²)
  3. O(n)
  4. O(n²)

Jawapan: O(n²). Untuk n yang besar sebutan n² mendominasi, dan faktor malar 2 dibuang. O(n) mengekalkan sebutan yang salah, dan O(2n²) terlupa membuang pemalar.

3Carian, pengisihan dan rekursi

Beberapa algoritma muncul dalam hampir setiap kursus. Pelajari kerumitannya sebagai fakta.

  • Carian linear menyemak item satu demi satu: O(n). Carian binari memerlukan tatasusunan yang telah diisih dan membahagi dua julat pada setiap langkah: O(log n).
  • Isihan gelembung, sisipan dan pilihan membandingkan dan menukar item dalam gelung bersarang: O(n²). Isihan sisipan ialah O(n) pada tatasusunan yang sudah diisih.
  • Isihan gabung memecahkan tatasusunan kepada dua bahagian, mengisihnya dan menggabungkannya: O(n log n) dalam setiap kes, dengan memori tambahan O(n).
  • Isihan pantas memecahkan di sekeliling pangsi: O(n log n) secara purata, tetapi O(n²) dalam kes terburuk, contohnya tatasusunan yang sudah diisih dengan elemen pertama sebagai pangsi.
  • Tiada isihan yang hanya membandingkan item boleh mengatasi Ω(n log n) dalam kes terburuk. Isihan bilangan lebih pantas kerana ia tidak membandingkan.

Fungsi rekursif memanggil dirinya sendiri pada input yang lebih kecil sehingga mencapai kes asas yang dijawabnya secara terus. Masa larinya ditulis sebagai hubungan jadi semula:

  • T(n) = T(n/2) + O(1) memberi O(log n), seperti carian binari.
  • T(n) = 2T(n/2) + O(n) memberi O(n log n), seperti isihan gabung.
  • T(n) = T(n − 1) + O(n) memberi O(n²).
  • T(n) = 2T(n − 1) + O(1) memberi O(2ⁿ).

Tiga idea reka bentuk wajar diketahui. Pecah dan takluk memecah, menyelesaikan dan menggabungkan. Tamak mengambil pilihan terbaik setempat pada setiap langkah. Pengaturcaraan dinamik menyimpan jawapan bagi submasalah bertindih supaya ia dikira sekali sahaja.

Semakan kendiri Apakah kerumitan masa kes terburuk bagi isihan pantas?
  1. O(log n)
  2. O(n log n)
  3. O(n)
  4. O(n²)

Jawapan: O(n²). Dengan pangsi yang buruk setiap pemecahan meninggalkan n − 1 item di satu sebelah, yang memberi O(n²). O(n log n) ialah kes puratanya, dan kes terburuk bagi isihan gabung.

4Kaedah langkah demi langkah

Untuk mencari kerumitan masa bagi sekeping kod:

  1. Tentukan apakah n: saiz input.
  2. Kira berapa kali setiap gelung berjalan. Gelung yang menambah 1 setiap kali berjalan kira-kira n kali. Gelung yang menggandakan atau membahagi dua berjalan kira-kira log₂ n kali.
  3. Gelung di dalam gelung lain didarabkan. Gelung yang berturutan ditambah.
  4. Bagi fungsi rekursif, tulis hubungan jadi semula: berapa banyak panggilan, pada saiz apa, tambah kerja bagi setiap panggilan.
  5. Kekalkan sebutan yang tumbuh paling pantas dan buang pemalar.
  6. Semak dengan nombor kecil, contohnya n = 8 atau n = 1024.

Untuk soalan teori, namakan dahulu algoritma atau idea yang diterangkannya, kemudian ingat kerumitannya dan syaratnya (input terisih, pemberat bukan negatif, submasalah bertindih).

5Contoh terselesai

Ikuti setiap langkah. Cuba ramalkan langkah seterusnya sebelum anda membukanya.

Contoh terselesai

Apakah kerumitan masa kod ini? for i = 1 to n: (j = 1; while j < n: j = j × 2)

1

Namakan saiz input

n ialah nombor yang menjadi had gelung.

2

Kira gelung luar

i bergerak dari 1 hingga n dengan langkah 1, maka gelung luar berjalan n kali.

3

Kira gelung dalam

j mengambil nilai 1, 2, 4, 8, … dan berhenti apabila mencapai n. Selepas k pusingan j = 2k, maka gelung berhenti selepas kira-kira log₂ n pusingan.

4

Gabungkan gelung

Gelung dalam berada di dalam gelung luar, maka bilangannya didarabkan.

n · log₂ n ⇒ O(n log n)
5

Semak dengan nombor

Untuk n = 1024 gelung dalam berjalan log₂ 1024 = 10 kali, maka badan gelung berjalan 1024 · 10 = 10 240 kali. Itu jauh kurang daripada n² = 1 048 576.

Jawapan

O(n log n)

6Kesilapan lazim

  • Mendarabkan gelung yang berjalan berturutan. n + n = 2n masih O(n).
  • Mengekalkan pemalar, seperti dalam O(2n) atau O(n/2). Kedua-duanya O(n).
  • Mengira gelung penggandaan sebagai n pusingan. Ia berjalan kira-kira log₂ n kali.
  • Menggunakan carian binari pada data yang tidak diisih, atau pada senarai terpaut yang bahagian tengahnya tidak boleh dicapai dalam satu langkah.
  • Memberi kes purata isihan pantas apabila kes terburuk yang diminta.
  • Menyangka Big O bermaksud “tepat”. O(n²) ialah batas atas; Θ(n²) ialah pertumbuhan yang tepat.
Semakan kendiri Sebuah fungsi menjalankan satu gelung n lelaran dan kemudian, secara berasingan, satu lagi gelung n lelaran. Apakah kerumitan masanya?
  1. O(2n)
  2. O(log n)
  3. O(n)
  4. O(n²)

Jawapan: O(n). Gelung berturutan ditambah: n + n = 2n, dan pemalar dibuang, maka O(n). O(n²) hanya betul jika satu gelung berada di dalam gelung yang lain.

7Rupa soalan peperiksaan

  • Mudah: istilah dan fakta utama. Kerumitan carian binari, isihan gabung atau akses tatasusunan, maksud O, Ω dan Θ, apakah rekursi.
  • Sederhana: menerapkan konsep. Kerumitan serpihan kod, hubungan jadi semula untuk diselesaikan, bagaimana masa berubah apabila n digandakan, algoritma mana yang sesuai untuk sesuatu tugas.
  • Sukar: kes dan analisis. Teorem induk, kes terburuk isihan pantas, tamak berbanding pengaturcaraan dinamik, dan kelas P, NP dan NP-lengkap.

P mengandungi masalah yang boleh diselesaikan dalam masa polinomial. NP mengandungi masalah yang penyelesaiannya boleh disemak dalam masa polinomial. Setiap masalah dalam P berada dalam NP; sama ada P = NP masih tidak diketahui.

Belajar langkah demi langkah dalam aplikasiBelajar langkah demi langkah dalam aplikasi

Contoh soalan

Contoh 1Mudah

Notasi manakah yang menerangkan batas atas pertumbuhan?

  1. ABig Omega
  2. BOmega kecil
  3. CBig O
  4. DBig Theta
Tunjukkan petunjuk
  1. "Paling banyak".
  2. Dua jawapan salah kini telah dipangkah. Satu daripada dua yang tinggal adalah betul.
Tunjukkan jawapan dan penerangan

Mengapa ini jawapannya

O memberikan batas atas, Ω batas bawah dan Θ batas ketat.

Jawapan

C · Big O
Contoh 2Sederhana

Dalam tatasusunan tersusun, anda mencari dua elemen yang jumlahnya sama dengan sasaran dengan menggerakkan satu penunjuk dari setiap hujung ke dalam. Apakah kerumitan masanya?

  1. AO(n)
  2. BO(n log n)
  3. CO(n²)
  4. DO(log n)
Tunjukkan petunjuk
  1. Setiap langkah menggerakkan satu penunjuk satu kedudukan.
  2. Dua jawapan salah kini telah dipangkah. Satu daripada dua yang tinggal adalah betul.
Tunjukkan jawapan dan penerangan

Mengapa ini jawapannya

Jika jumlah terlalu kecil penunjuk kiri bergerak ke kanan, jika terlalu besar penunjuk kanan bergerak ke kiri, jadi terdapat paling banyak n langkah.

Jawapan

A · O(n)
Contoh 3Sukar

Algoritma Strassen mendarab matriks menggunakan 7 dan bukannya 8 pendaraban rekursif blok separuh saiz. Apakah masa larinya?

  1. AΘ(n² log n)
  2. BΘ(n2)
  3. CΘ(n³)
  4. DΘ(nlog₂ 7), kira-kira n2.81
Tunjukkan petunjuk
  1. Hubungan jadi semulanya ialah T(n) = 7T(n/2) + O(n²).
  2. Dua jawapan salah kini telah dipangkah. Satu daripada dua yang tinggal adalah betul.
Tunjukkan jawapan dan penerangan

Mengapa ini jawapannya

Dengan a = 7 dan b = 2, nlog₂ 7 mendominasi kerja penambahan O(n²), memberikan kira-kira n2.81.

Jawapan

D · Θ(nlog₂ 7), kira-kira n2.81

Soalan dan jawapan

Apakah Algoritma & kerumitan?

Dua algoritma boleh menyelesaikan masalah yang sama tetapi mengambil masa yang sangat berbeza. Kerumitan menerangkan bagaimana kerja itu bertambah apabila input menjadi lebih besar.

Saiz input dipanggil n: bilangan item untuk diisih, panjang senarai, bilangan nod dalam graf.

Bagaimanakah saya mempelajari Algoritma & kerumitan langkah demi langkah?
  1. Apa yang diukur oleh kerumitan
  2. Big O dan kelas pertumbuhan
  3. Carian, pengisihan dan rekursi
  4. Kaedah langkah demi langkah
  5. Contoh terselesai
  6. Kesilapan lazim
  7. Rupa soalan peperiksaan
Apakah yang diliputi oleh latihan Algoritma & kerumitan?
  • Mudah: istilah dan fakta utama
  • Sederhana: menggunakan konsep
  • Sukar: kes dan analisis

Setiap soalan mempunyai empat pilihan, dan hanya satu yang betul. Buntu? Buka petunjuk kecil dahulu, dan penerangan penuh hanya apabila anda memerlukannya.

Cara latihan berfungsi

  • Setiap soalan mempunyai empat pilihan, dan hanya satu yang betul.
  • Buntu? Buka petunjuk kecil dahulu, dan penerangan penuh hanya apabila anda memerlukannya.
  • Kemajuan, kesilapan dan soalan tersimpan anda dikekalkan, jadi anda boleh menyemak sebelum peperiksaan.

Topik sebelum dan selepas topik ini

Teruskan dengan

Struktur data

Kursus dengan topik ini

Struktur Data dan AlgoritmaAsas Sains Komputer

Lebih banyak topik dalam Sains komputer

Sistem nomborSubnet IPv4Rangkaian komputerStruktur dataPangkalan data & SQL

Lembaran kerja boleh cetak

Lembaran kerja Algoritma & kerumitan dengan jawapan
Berlatih Algoritma & kerumitan secara percumaBerlatih Algoritma & kerumitan sekarang5 soalan percuma setiap hari. Tiada kad diperlukan.