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

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

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

ข้อใดเติบโตช้าที่สุดเมื่อ n มีค่ามาก

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

ลูปเริ่มที่ i = 1 และเพิ่ม i เป็นสองเท่าทุกรอบจนกระทั่ง i > n ลูปนี้ทำงานกี่รอบ

1. Aประมาณ n
2. Bประมาณ n / 2
3. Cประมาณ n²
4. Dประมาณ log₂ n

ข้อใดเกี่ยวกับฟังก์ชันเรียกซ้ำที่ไม่มีกรณีฐานที่ไปถึงได้ถูกต้อง

1. Aเรียกตัวเองต่อไปจนสแต็กการเรียกล้น
2. Bคอมไพเลอร์แปลงเป็นลูปที่จบอย่างปลอดภัยเสมอ
3. Cคืนค่า 0 โดยอัตโนมัติ
4. Dทำงานในเวลา O(1)

การค้นหาแบบทวิภาคต้องเปรียบเทียบประมาณกี่ครั้งในกรณีเลวร้ายที่สุดบนอาร์เรย์ที่เรียงแล้วซึ่งมี 1,000,000 สมาชิก

1. Aประมาณ 500,000
2. Bประมาณ 20
3. Cประมาณ 100
4. Dประมาณ 1,000

อัลกอริทึม Floyd–Warshall คำนวณอะไรและเร็วเพียงใด

1. Aต้นไม้ทอดข้ามที่น้อยที่สุดใน O(E log V)
2. Bลำดับทอพอโลยีใน O(V²)
3. Cเส้นทางสั้นที่สุดจากจุดยอดต้นทางหนึ่งไปยังจุดยอดอื่นทั้งหมดใน O(V + E)
4. Dเส้นทางสั้นที่สุดระหว่างจุดยอดทุกคู่ใน O(V³)

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

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

ข้อใดเกี่ยวกับ P และ NP ถูกต้อง

1. Aปัญหา NP ตรวจสอบอย่างรวดเร็วไม่ได้
2. BNP หมายถึง "ไม่ใช่พหุนาม"
3. Cได้พิสูจน์แล้วว่า P ≠ NP
4. Dทุกปัญหาใน P อยู่ใน NP ด้วย