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

counting sort สำหรับจำนวนเต็ม n ตัวในช่วง 0 ถึง k ใช้เวลาเท่าใด

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

กรณีฐานของฟังก์ชันเรียกซ้ำคืออะไร

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

selection sort ทำงานอย่างไร

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

อัลกอริทึมการเรียงลำดับใดเป็นแบบเสถียร (stable)

1. ASelection sort (แบบทั่วไป)
2. BHeap sort
3. CMerge sort
4. DQuicksort (แบบทำในที่เดิมทั่วไป)

ความซับซ้อนเชิงเวลาของอัลกอริทึม Bellman–Ford บนกราฟที่มี V จุดยอดและ E เส้นเชื่อมคือเท่าใด

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

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

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

นิยามใดของคลาส P ถูกต้อง

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

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

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