ใบงาน อัลกอริทึมและความซับซ้อน พร้อมเฉลย

อัลกอริทึมการเรียงลำดับใดสลับสมาชิกที่อยู่ติดกันซึ่งเรียงผิดลำดับซ้ำ ๆ

1. Aการเรียงแบบฮีป (heap sort)
2. Bการเรียงแบบเร็ว (quicksort)
3. Cการเรียงแบบฟอง (bubble sort)
4. Dการเรียงแบบผสาน (merge sort)

อัลกอริทึมกำลังเดรัจฉาน (brute force) คืออะไร

1. Aอัลกอริทึมที่ทำงานบนหลายตัวประมวลผล
2. Bอัลกอริทึมที่เดาคำตอบแบบสุ่ม
3. Cอัลกอริทึมที่ใช้การเรียกซ้ำเสมอ
4. Dอัลกอริทึมที่ลองคำตอบผู้สมัครที่เป็นไปได้ทั้งหมด

อัลกอริทึมที่มีลูปซ้อนกันสองชั้น แต่ละชั้นทำงาน n รอบ โดยทั่วไปมีความซับซ้อนเท่าใด

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

การวิเคราะห์แบบกระจายต้นทุน (amortised analysis) วัดสิ่งใด

1. Aต้นทุนคาดหมายเหนืออินพุตสุ่ม
2. Bต้นทุนเฉลี่ยต่อหนึ่งการดำเนินการ บนลำดับการดำเนินการที่เลวร้ายที่สุด
3. Cต้นทุนของอัลกอริทึมบนอินพุตที่ดีที่สุด
4. Dต้นทุนของการดำเนินการเดียวที่แพงที่สุดในลำดับการดำเนินการ

เหตุใดจึงมักละฐานของลอการิทึมใน Big O เช่น O(log n)

1. Aฐานมีความสำคัญเฉพาะเมื่อ n น้อย
2. Bลอการิทึมทั้งหมดในวิทยาการคอมพิวเตอร์มีฐาน 10 จึงไม่ต้องระบุ
3. Cลอการิทึมที่ฐานต่างกันต่างกันเพียงตัวคูณคงที่
4. Dลอการิทึมถูกปัดเป็นจำนวนเต็มเสมอ

อัลกอริทึมใดหาเส้นทางสั้นที่สุดจากต้นทางหนึ่งในกราฟที่น้ำหนักเส้นเชื่อมไม่เป็นลบ

1. Aอัลกอริทึมของ Kruskal
2. Bอัลกอริทึมของ Dijkstra
3. Cต้องใช้ Bellman–Ford ในทุกกรณี
4. Dการค้นหาในแนวลึก

เวลาทำงานของอัลกอริทึมของ Dijkstra ที่ใช้ฮีปไบนารีบนกราฟที่มี V จุดยอดและ E เส้นเชื่อมคือเท่าใด

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

ปัญหา 0/1 knapsack ที่แก้ด้วยการโปรแกรมพลวัตใช้เวลา O(nW) เหตุใดจึงเรียกว่าเวลาแบบกึ่งพหุนาม (pseudo-polynomial)

1. Aเพราะใช้ได้เฉพาะ W = 0
2. Bเพราะ n มีค่าน้อยเสมอ
3. CW เป็นตัวเลข เวลาจึงเป็นเอกซ์โพเนนเชียลเมื่อเทียบกับจำนวนบิตที่ใช้เขียน W
4. Dเพราะอัลกอริทึมเป็นแบบสุ่มและเวลาทำงานแปรผันไปตามอินพุตแต่ละครั้ง