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

memoisation คืออะไร

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

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

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

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

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

ความซับซ้อนเชิงเวลาของ for i = 1 to n: (j = 1; while j < n: j = j × 2) คือเท่าใด

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

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

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

ความซับซ้อนเชิงเวลาของการคำนวณจำนวนฟีโบนักชีตัวที่ n ด้วยตารางแบบล่างขึ้นบนคือเท่าใด

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

อัลกอริทึมของ Strassen คูณเมทริกซ์โดยใช้การคูณแบบเรียกซ้ำของบล็อกครึ่งขนาด 7 ครั้งแทนที่จะเป็น 8 ครั้ง เวลาทำงานของมันคือเท่าใด

1. AΘ(n² log n)
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n^{log₂ 7}) ประมาณ n^2.81

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

1. AΘ(n log² n)
2. BΘ(n)
3. CΘ(n log n)
4. DΘ(n²)