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

merge sort แบบมาตรฐานที่ใช้อาร์เรย์ใช้หน่วยความจำเพิ่มเติมเท่าใด

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

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

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

การเติบโตแบบ O(2ⁿ) เรียกว่าอะไร

1. Aเอกซ์โพเนนเชียล
2. Bเชิงเส้น
3. Cลอการิทึม
4. Dพหุนาม

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

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

คุณเรียงอาร์เรย์ n สมาชิกหนึ่งครั้ง แล้วตอบคำถามการเป็นสมาชิก k ข้อด้วยการค้นหาแบบทวิภาค ต้นทุนรวมเท่าใด

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

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

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

เหตุใดการค้นหาแบบทวิภาคจึงไม่ให้เวลา O(log n) บนรายการเชื่อมโยงเดี่ยว

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

ทฤษฎีบท Cook–Levin พิสูจน์สิ่งใด

1. Aปัญหาการหยุดตัดสินไม่ได้
2. BP ไม่เท่ากับ NP
3. Cปัญหาความสอดคล้องของสูตรบูลีน (SAT) เป็น NP-complete
4. Dทุกปัญหา NP แก้ได้ในเวลาเอกซ์โพเนนเชียล