Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah algoritma?

1. AJujukan langkah yang terhingga dan jelas ditakrifkan yang menyelesaikan masalah
2. BBahasa pengaturcaraan yang direka untuk menulis formula matematik
3. CMana-mana program komputer yang mempunyai antara muka grafik
4. DStruktur data yang menyimpan nombor

Bagaimanakah isihan pemilihan berfungsi?

1. AIa menyisipkan setiap elemen ke dalam bahagian tersusun yang berkembang dengan menganjak
2. BIa berulang kali menukar elemen jiran yang berada dalam susunan salah
3. CIa berulang kali mencari minimum bahagian tidak tersusun dan menukarnya ke hadapan
4. DIa membahagikan tatasusunan kepada dua dan mencantumkannya

Apakah tiga langkah algoritma bahagi dan takluk?

1. ABaca, kira, tulis
2. BIsih, cari, kembali
3. CTeka, semak, ulang
4. DBahagi, takluk, gabung

Apakah yang dikira oleh algoritma Floyd–Warshall, dan sepantas mana?

1. ALaluan terpendek dari satu bucu sumber ke semua bucu lain dalam O(V + E)
2. BLaluan terpendek antara semua pasangan bucu dalam O(V³)
3. CPokok rentang minimum dalam O(E log V)
4. DSusunan topologi dalam O(V²)

Apakah penyelesaian hubungan jadi semula T(n) = 2T(n − 1) + O(1)?

1. AO(n)
2. BO(n log n)
3. CO(2ⁿ)
4. DO(n²)

Apakah kerumitan masa algoritma Bellman–Ford pada graf dengan V bucu dan E sisi?

1. AO(V × E)
2. BO(V³ × E)
3. CO(V + E)
4. DO(E log V)

Pendaraban Karatsuba memenuhi T(n) = 3T(n/2) + O(n). Apakah penyelesaiannya?

1. AΘ(n²)
2. BΘ(n³)
3. CΘ(n^{log₂ 3}), kira-kira n^1.585
4. DΘ(n log n)

Sesuatu masalah ialah NP-lengkap jika ia:

1. ADalam NP dan setiap masalah NP boleh diturunkan kepadanya dalam masa polinomial
2. BBoleh diselesaikan dalam masa polinomial
3. CMustahil diselesaikan
4. DDi luar NP tetapi lebih sukar daripada semua masalah NP, seperti masalah penghentian