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

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

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

เวลาทำงานของอัลกอริทึมเป็น O(n) การเติบโตแบบนี้เรียกว่าอะไร

1. Aเชิงเส้น
2. Bลอการิทึม
3. Cกำลังสอง
4. Dคงที่

ความซับซ้อนเชิงเวลาของการหาค่าที่มากที่สุดในอาร์เรย์ที่ไม่เรียงลำดับซึ่งมีตัวเลข n ตัวคือเท่าใด

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

ความซับซ้อนเชิงเวลาในกรณีเลวร้ายที่สุดของ quicksort คือเท่าใด

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

ความสัมพันธ์เวียนเกิด T(n) = T(n/2) + O(1) มีผลเฉลยเป็นเท่าใด

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

ความสัมพันธ์เวียนเกิด T(n) = 2T(n/2) + O(1) มีผลเฉลยเป็นเท่าใด

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

เทคนิคใดให้เวลาทำงานคาดหมาย O(n log n) ของ quicksort กับอินพุตใด ๆ

1. Aเลือกสมาชิกตัวแรกเสมอ
2. Bเรียกซ้ำเฉพาะฝั่งซ้าย
3. Cเลือกตัวหลักแบบสุ่มสม่ำเสมอ
4. Dเรียงอินพุตก่อนรัน quicksort

เหตุใดอัลกอริทึมของ Dijkstra จึงอาจให้ผลผิดเมื่อน้ำหนักเส้นเชื่อมบางเส้นติดลบ

1. Aตัวเลขติดลบเก็บในคิวลำดับความสำคัญไม่ได้
2. Bใช้ได้กับกราฟไม่มีทิศทางเท่านั้น
3. Cจุดยอดถูกตรึงค่าเมื่อถูกดึงออก แต่เส้นเชื่อมติดลบที่มาทีหลังอาจให้เส้นทางที่สั้นกว่าแก่มัน
4. Dเข้าสู่ลูปไม่สิ้นสุดทุกครั้งที่พบเส้นเชื่อมติดลบ