Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah Big O bagi 3n² + 5n + 2?

1. AO(3n²)
2. BO(n³)
3. CO(5n)
4. DO(n²)

Apakah maksudnya jika sesuatu operasi berjalan dalam masa O(1)?

1. AIa memproses tepat satu elemen bagi setiap saat masa larian
2. BMasa larinya tidak bertambah dengan saiz input
3. CIa hanya boleh dijalankan sekali
4. DIa sentiasa mengambil tepat satu saat

Mengakses elemen mengikut indeks dalam tatasusunan mengambil masa:

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

Betulkah untuk mengatakan bahawa algoritma O(n²) juga O(n³)?

1. ATidak, kerana Big O mesti sentiasa menyatakan kadar pertumbuhan yang tepat bagi fungsi itu
2. BTidak, kerana n³ lebih kecil daripada n² untuk n yang besar
3. CYa, tetapi hanya jika n kurang daripada 100
4. DYa, kerana Big O ialah batas atas dan n² tumbuh tidak lebih pantas daripada n³

Apakah kerumitan masa bagi: for i = 1 to n: for j = 1 to i: lakukan kerja O(1)?

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

Bagaimanakah algoritma Prim membina pokok rentang minimum?

1. AIa menjalankan carian pertama lebar dan mengekalkan pokok BFS
2. BIa menumbuhkan satu pokok dari bucu permulaan, dengan menambah sisi termurah yang meninggalkan pokok
3. CIa membuang sisi paling mahal sehingga tiada kitaran tinggal
4. DIa mengisih semua sisi mengikut pemberat dan menambah setiap satu kecuali jika ia membentuk kitaran dalam hutan

Masalah penghentian (halting problem) menunjukkan bahawa:

1. ASetiap program akhirnya berhenti
2. BTiada algoritma yang dapat memutuskan bagi setiap program dan input sama ada ia berhenti
3. CSesetengah program berjalan lebih pantas pada komputer yang lebih pantas, jadi penghentian bergantung pada perkakasan
4. DGelung harus dielakkan

Mengambil kedua-dua hujung setiap sisi dalam padanan maksimal memberikan litupan bucu. Sebaik manakah litupan ini?

1. AMutunya tidak diketahui berbanding optimum
2. BPaling banyak log n kali minimum
3. CSentiasa litupan bucu minimum
4. DPaling banyak dua kali ganda saiz litupan bucu minimum