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

ใบงาน อัลกอริทึมและความซับซ้อน ฟรีสำหรับพิมพ์: 8 ข้อ ตั้งแต่ระดับง่ายถึงระดับข้อสอบจริง พร้อมเฉลย พิมพ์หรือบันทึกเป็น PDF ได้

ใบงานใหม่ฝึกออนไลน์พร้อมคำใบ้

สำหรับผู้สอน: พิมพ์ ทำสำเนา และใช้ในชั้นเรียนได้ฟรี ใบงานใหม่แต่ละชุดมีค่าตัวเลขใหม่และเฉลยของตัวเอง หากใส่ลิงก์ไปยัง ExamProblems ในหน้ารายวิชาของคุณ เราจะขอบคุณมาก

ชื่อ: ____________________   วันที่: ____________

1.ง่าย

เวลาทำงานในกรณีเฉลี่ยอธิบายสิ่งใด

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

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

  1. AO(n)
  2. BO(log n)
  3. CO(n²)
  4. DO(n log n)
3.ง่าย

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

  1. AO(2n)
  2. BO(n²)
  3. CO(log n)
  4. DO(n)
4.ปานกลาง

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

  1. AO(n)
  2. BO(log n)
  3. CO(n²)
  4. DO(n log n)
5.ปานกลาง

ฟังก์ชันแฟกทอเรียลแบบเรียกซ้ำง่าย ๆ fact(n) = n × fact(n − 1) ใช้พื้นที่สแต็กเท่าใด

  1. AO(1)
  2. BO(log n)
  3. CO(n)
  4. DO(n²)
6.ปานกลาง

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

  1. AO(log n)
  2. BO(n²)
  3. CO(2ⁿ)
  4. DO(n)
7.ยาก

โดยใช้ทฤษฎีบทหลัก T(n) = 8T(n/2) + O(n²) มีผลเฉลยเป็น

  1. AΘ(n log n)
  2. BΘ(n²)
  3. CΘ(n² log n)
  4. DΘ(n³)
8.ยาก

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

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

เฉลย

  1. 1. B · เวลาคาดหมายภายใต้การแจกแจงของอินพุตขนาด n ที่กำหนด
  2. 2. B · O(log n)
  3. 3. B · O(n²)
  4. 4. C · O(n²)
  5. 5. C · O(n)
  6. 6. D · O(n)
  7. 7. D · Θ(n³)
  8. 8. A · เลือกตัวหลักแบบสุ่มสม่ำเสมอ

เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com