อัลกอริทึมและความซับซ้อน: ข้อสอบฝึกหัดพร้อมคำอธิบาย

ข้อสอบปรนัย อัลกอริทึมและความซับซ้อน ฟรี พร้อมคำใบ้และคำอธิบาย สามระดับ: ศัพท์สำคัญและข้อเท็จจริง, การประยุกต์ใช้แนวคิด, กรณีศึกษาและการวิเคราะห์

โจทย์ฝึกฟรีง่าย

ชั้นความซับซ้อนใดเติบโตเร็วที่สุดเมื่อ n มีค่ามาก

โจทย์ถัดไป →
ฝึก อัลกอริทึมและความซับซ้อน ฟรีฝึก อัลกอริทึมและความซับซ้อน เลยโจทย์ฟรีวันละ 5 ข้อ ไม่ต้องใช้บัตร

สิ่งที่คุณจะได้ฝึก

  1. ง่ายศัพท์สำคัญและข้อเท็จจริง
  2. ปานกลางการประยุกต์ใช้แนวคิด
  3. ยากกรณีศึกษาและการวิเคราะห์

เรียนรู้ อัลกอริทึมและความซับซ้อน ตั้งแต่ต้น

1ความซับซ้อนวัดอะไร

อัลกอริทึม (algorithm) คือรายการขั้นตอนที่แม่นยำและมีจำนวนจำกัดซึ่งแก้ปัญหาหนึ่ง เช่น เรียงลำดับรายการหรือหาชื่อในสมุดโทรศัพท์

อัลกอริทึมสองแบบอาจแก้ปัญหาเดียวกันแต่ใช้เวลาต่างกันมาก ความซับซ้อนอธิบายว่างานที่ต้องทำเพิ่มขึ้นอย่างไรเมื่ออินพุตใหญ่ขึ้น

ขนาดของอินพุตเรียกว่า n คือจำนวนรายการที่ต้องเรียงลำดับ ความยาวของรายการ หรือจำนวนโหนดในกราฟ

ลองนึกถึงการหาชื่อในสมุดโทรศัพท์ 1000 หน้า การอ่านทุกหน้าใช้ถึง 1000 ขั้นตอน การเปิดตรงกลางแล้วแบ่งครึ่งทุกครั้งใช้ประมาณ 10 ขั้นตอน

ความซับซ้อนเชิงเวลา (time complexity) นับจำนวนขั้นตอน ความซับซ้อนเชิงพื้นที่ (space complexity) นับหน่วยความจำเพิ่มเติม ทั้งสองเขียนเป็นฟังก์ชันของ n

โดยปกติเราดูกรณีเลวร้ายที่สุด คือการทำงานมากที่สุดในอินพุตทุกแบบที่มีขนาด n บางครั้งโจทย์ถามกรณีเฉลี่ยหรือกรณีดีที่สุดแทน

ตรวจสอบตนเอง อัลกอริทึมที่งานเพิ่มขึ้นแบบ n² ใช้เวลา 1 วินาทีเมื่อ n = 1000 เมื่อ n = 2000 จะใช้เวลาประมาณเท่าใด
  1. 1 วินาที
  2. 2 วินาที
  3. 4 วินาที
  4. 8 วินาที

คำตอบ: 4 วินาที. เมื่อ n เป็นสองเท่า n² จะเป็น 2² = 4 เท่า เวลาจึงเปลี่ยนจากประมาณ 1 เป็นประมาณ 4 วินาที 2 วินาทีเป็นคำตอบของการเติบโตแบบเชิงเส้น และ 8 สำหรับ n³

2บิ๊กโอและกลุ่มอัตราการเติบโต

สัญกรณ์ บิ๊กโอ (Big O) เก็บเฉพาะสิ่งที่สำคัญเมื่อ n มีค่ามาก ตัดตัวประกอบที่เป็นค่าคงที่ทิ้งและเก็บเฉพาะพจน์ที่โตเร็วที่สุด

3n² + 5n + 2 ⇒ O(n²)

เมื่อ n = 1000 พจน์ n² มีค่า 3 000 000 ขณะที่ 5n มีเพียง 5000 พจน์ที่เล็กกว่าแทบไม่เปลี่ยนผลรวม

กลุ่มเหล่านี้ปรากฏซ้ำแล้วซ้ำอีก เรียงจากโตช้าที่สุดไปเร็วที่สุด:

  • O(1) ค่าคงที่: การอ่านสมาชิกของอาร์เรย์ด้วยดัชนี
  • O(log n) ลอการิทึม: การค้นหาแบบทวิภาค (binary search) ซึ่งแบ่งปัญหาครึ่งหนึ่งทุกขั้น
  • O(n) เชิงเส้น: การวนผ่านทุกรายการหนึ่งรอบ เช่น การหาค่ามากที่สุด
  • O(n log n): อัลกอริทึมเรียงลำดับที่ดี เช่น merge sort
  • O(n²) กำลังสอง: ลูปสองชั้นซ้อนกันบนรายการ เช่น bubble sort
  • O(2ⁿ) เอกซ์โปเนนเชียล: การลองทุกเซตย่อย ใช้งานไม่ได้อย่างรวดเร็ว
ntlog nnn log nn²2ⁿ

บิ๊กโอเป็นขอบเขตบน: งานโตไม่เร็วกว่านี้ Ω (บิ๊กโอเมกา) เป็นขอบเขตล่าง และ Θ (ทีตา) เป็นขอบเขตแน่น ทั้งบนและล่าง

ฐานของลอการิทึมไม่สำคัญในบิ๊กโอ เพราะลอการิทึมที่มีฐานต่างกันต่างกันเพียงตัวประกอบที่เป็นค่าคงที่

ตรวจสอบตนเอง บิ๊กโอของ 4n + 2n² + 100 คืออะไร
  1. O(100)
  2. O(2n²)
  3. O(n)
  4. O(n²)

คำตอบ: O(n²). เมื่อ n มาก พจน์ n² เป็นตัวชี้ขาด และตัวประกอบคงที่ 2 ถูกตัดทิ้ง O(n) เก็บพจน์ผิด และ O(2n²) ลืมตัดค่าคงที่

3การค้นหา การเรียงลำดับ และการเรียกซ้ำ

อัลกอริทึมบางแบบปรากฏในแทบทุกวิชา ให้จำความซับซ้อนของมันเป็นข้อเท็จจริง

  • การค้นหาเชิงเส้น (linear search) ตรวจรายการทีละรายการ: O(n) การค้นหาแบบทวิภาค ต้องใช้อาร์เรย์ที่เรียงลำดับแล้ว และแบ่งช่วงครึ่งหนึ่งทุกขั้น: O(log n)
  • Bubble, insertion และ selection sort เปรียบเทียบและสลับรายการในลูปซ้อน: O(n²) Insertion sort เป็น O(n) บนอาร์เรย์ที่เรียงลำดับแล้ว
  • Merge sort แบ่งอาร์เรย์เป็นครึ่ง เรียงลำดับแต่ละครึ่งแล้วผสานกัน: O(n log n) ในทุกกรณี และใช้หน่วยความจำเพิ่ม O(n)
  • Quicksort แบ่งรอบค่าหลัก (pivot): O(n log n) โดยเฉลี่ย แต่ O(n²) ในกรณีเลวร้ายที่สุด เช่น อาร์เรย์ที่เรียงลำดับแล้วโดยใช้สมาชิกตัวแรกเป็น pivot
  • ไม่มีการเรียงลำดับที่อาศัยการเปรียบเทียบอย่างเดียวที่จะเร็วกว่า Ω(n log n) ในกรณีเลวร้ายที่สุด Counting sort เร็วกว่าเพราะไม่เปรียบเทียบ

ฟังก์ชันเรียกซ้ำ (recursive) เรียกตัวเองด้วยอินพุตที่เล็กลงจนถึงกรณีฐาน (base case) ที่ตอบได้โดยตรง เวลาทำงานของมันเขียนเป็นความสัมพันธ์เวียนเกิด (recurrence):

  • T(n) = T(n/2) + O(1) ให้ O(log n) เหมือน binary search
  • T(n) = 2T(n/2) + O(n) ให้ O(n log n) เหมือน merge sort
  • T(n) = T(n − 1) + O(n) ให้ O(n²)
  • T(n) = 2T(n − 1) + O(1) ให้ O(2ⁿ)

แนวคิดการออกแบบสามอย่างที่ควรรู้ แบ่งแยกและเอาชนะ (divide and conquer) แบ่ง แก้ และรวม โลภ (greedy) เลือกทางที่ดีที่สุดเฉพาะที่ในแต่ละขั้น การโปรแกรมเชิงพลวัต (dynamic programming) เก็บคำตอบของปัญหาย่อยที่ซ้อนทับกันเพื่อให้คำนวณเพียงครั้งเดียว

ตรวจสอบตนเอง ความซับซ้อนเชิงเวลาของ quicksort ในกรณีเลวร้ายที่สุดคืออะไร
  1. O(log n)
  2. O(n log n)
  3. O(n)
  4. O(n²)

คำตอบ: O(n²). ถ้า pivot ไม่ดี ทุกการแบ่งจะเหลือ n − 1 รายการอยู่ด้านเดียว ซึ่งให้ O(n²) ส่วน O(n log n) เป็นกรณีเฉลี่ยของมัน และเป็นกรณีเลวร้ายที่สุดของ merge sort

4วิธีทำทีละขั้น

เพื่อหาความซับซ้อนเชิงเวลาของโค้ดชิ้นหนึ่ง:

  1. กำหนดว่า n คืออะไร: ขนาดของอินพุต
  2. นับว่าแต่ละลูปทำงานกี่ครั้ง ลูปที่เพิ่มทีละ 1 ทำงานประมาณ n ครั้ง ลูปที่คูณสองหรือหารสองทำงานประมาณ log₂ n ครั้ง
  3. ลูปที่ซ้อนกันให้คูณ ลูปที่ตามกันให้บวก
  4. สำหรับฟังก์ชันเรียกซ้ำ ให้เขียนความสัมพันธ์เวียนเกิด: เรียกกี่ครั้ง ด้วยขนาดเท่าใด บวกงานต่อการเรียกหนึ่งครั้ง
  5. เก็บพจน์ที่โตเร็วที่สุดและตัดค่าคงที่
  6. ตรวจด้วยจำนวนน้อย ๆ เช่น n = 8 หรือ n = 1024

สำหรับคำถามทฤษฎี ให้ระบุอัลกอริทึมหรือแนวคิดที่คำถามอธิบายก่อน แล้วนึกถึงความซับซ้อนและเงื่อนไขของมัน (อินพุตที่เรียงลำดับ น้ำหนักไม่เป็นลบ ปัญหาย่อยที่ซ้อนทับกัน)

5ตัวอย่างที่แก้ให้ดู

ทำตามทุกขั้นตอน ลองทำนายขั้นถัดไปก่อนเปิดดู

ตัวอย่างที่แก้ให้ดู

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

1

ระบุขนาดอินพุต

n คือจำนวนที่ลูปวิ่งไปถึง

2

นับลูปนอก

i เปลี่ยนจาก 1 ถึง n ทีละ 1 ลูปนอกจึงทำงาน n ครั้ง

3

นับลูปใน

j มีค่า 1, 2, 4, 8, … และหยุดเมื่อถึง n หลังจาก k รอบ j = 2k ลูปจึงหยุดหลังประมาณ log₂ n รอบ

4

รวมลูปเข้าด้วยกัน

ลูปในอยู่ภายในลูปนอก จึงคูณจำนวนครั้งเข้าด้วยกัน

n · log₂ n ⇒ O(n log n)
5

ตรวจด้วยตัวเลข

เมื่อ n = 1024 ลูปในทำงาน log₂ 1024 = 10 ครั้ง ตัวลูปจึงทำงาน 1024 · 10 = 10 240 ครั้ง ซึ่งน้อยกว่า n² = 1 048 576 มาก

คำตอบ

O(n log n)

6ข้อผิดพลาดที่พบบ่อย

  • คูณลูปที่ทำงานตามกัน n + n = 2n ยังคงเป็น O(n)
  • เก็บค่าคงที่ เช่น O(2n) หรือ O(n/2) ทั้งสองคือ O(n)
  • นับลูปที่คูณสองเป็น n รอบ จริง ๆ ทำงานประมาณ log₂ n ครั้ง
  • ใช้ binary search กับข้อมูลที่ไม่ได้เรียงลำดับ หรือกับลิงก์ลิสต์ที่เข้าถึงตรงกลางในขั้นตอนเดียวไม่ได้
  • ตอบกรณีเฉลี่ยของ quicksort เมื่อโจทย์ถามกรณีเลวร้ายที่สุด
  • คิดว่าบิ๊กโอหมายถึง “เท่ากับพอดี” O(n²) เป็นขอบเขตบน ส่วน Θ(n²) คือการเติบโตที่แน่นอน
ตรวจสอบตนเอง ฟังก์ชันหนึ่งทำลูป n รอบ แล้วแยกต่างหากทำลูปอีก n รอบ ความซับซ้อนเชิงเวลาเป็นเท่าใด
  1. O(2n)
  2. O(log n)
  3. O(n)
  4. O(n²)

คำตอบ: O(n). ลูปที่ตามกันให้บวก: n + n = 2n และตัดค่าคงที่ จึงเป็น O(n) O(n²) จะถูกก็ต่อเมื่อลูปหนึ่งอยู่ในอีกลูปหนึ่ง

7ข้อสอบมีหน้าตาอย่างไร

  • ง่าย: ศัพท์และข้อเท็จจริงสำคัญ ความซับซ้อนของ binary search, merge sort หรือการเข้าถึงอาร์เรย์ ความหมายของ O, Ω และ Θ การเรียกซ้ำคืออะไร
  • ปานกลาง: การประยุกต์แนวคิด ความซับซ้อนของชิ้นส่วนโค้ด ความสัมพันธ์เวียนเกิดที่ต้องแก้ เวลาเปลี่ยนอย่างไรเมื่อ n เป็นสองเท่า อัลกอริทึมใดเหมาะกับงานหนึ่ง
  • ยาก: กรณีศึกษาและการวิเคราะห์ ทฤษฎีบทหลัก (master theorem) กรณีเลวร้ายที่สุดของ quicksort greedy เทียบกับ dynamic programming และคลาส P, NP และ NP-complete

P คือปัญหาที่แก้ได้ในเวลาพหุนาม NP คือปัญหาที่ตรวจสอบคำตอบได้ในเวลาพหุนาม ทุกปัญหาใน P อยู่ใน NP ส่วน P = NP หรือไม่ยังไม่ทราบ

เรียนรู้ทีละขั้นในแอปเรียนรู้ทีละขั้นในแอป

ตัวอย่างคำถาม

ตัวอย่างที่ 1ง่าย

สัญกรณ์ใดใช้อธิบายขอบเขตบนของอัตราการเติบโต

  1. ABig Omega
  2. BLittle omega
  3. CBig O
  4. DBig Theta
แสดงคำใบ้
  1. "มากที่สุดเท่ากับ"
  2. ตอนนี้ขีดฆ่าคำตอบที่ผิดสองข้อแล้ว หนึ่งในสองข้อที่เหลือเป็นคำตอบที่ถูก
แสดงคำตอบและคำอธิบาย

เหตุผลที่เป็นคำตอบนี้

O ให้ขอบเขตบน Ω ให้ขอบเขตล่าง และ Θ ให้ขอบเขตที่แน่นพอดี

คำตอบ

C · Big O
ตัวอย่างที่ 2ปานกลาง

ในอาร์เรย์ที่เรียงแล้ว คุณหาสองสมาชิกที่ผลรวมเท่ากับเป้าหมายโดยเลื่อนตัวชี้จากแต่ละปลายเข้าหากัน ความซับซ้อนเชิงเวลาคือเท่าใด

  1. AO(n)
  2. BO(n log n)
  3. CO(n²)
  4. DO(log n)
แสดงคำใบ้
  1. แต่ละขั้นเลื่อนตัวชี้หนึ่งตำแหน่ง
  2. ตอนนี้ขีดฆ่าคำตอบที่ผิดสองข้อแล้ว หนึ่งในสองข้อที่เหลือเป็นคำตอบที่ถูก
แสดงคำตอบและคำอธิบาย

เหตุผลที่เป็นคำตอบนี้

ถ้าผลรวมน้อยเกินไปตัวชี้ซ้ายเลื่อนไปขวา ถ้ามากเกินไปตัวชี้ขวาเลื่อนไปซ้าย จึงมีไม่เกิน n ขั้น

คำตอบ

A · O(n)
ตัวอย่างที่ 3ยาก

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

  1. AΘ(n² log n)
  2. BΘ(n2)
  3. CΘ(n³)
  4. DΘ(nlog₂ 7) ประมาณ n2.81
แสดงคำใบ้
  1. ความสัมพันธ์เวียนเกิดคือ T(n) = 7T(n/2) + O(n²)
  2. ตอนนี้ขีดฆ่าคำตอบที่ผิดสองข้อแล้ว หนึ่งในสองข้อที่เหลือเป็นคำตอบที่ถูก
แสดงคำตอบและคำอธิบาย

เหตุผลที่เป็นคำตอบนี้

เมื่อ a = 7 และ b = 2 ค่า nlog₂ 7 ครอบงำงานบวก O(n²) ได้ประมาณ n2.81

คำตอบ

D · Θ(nlog₂ 7) ประมาณ n2.81

คำถามและคำตอบ

อัลกอริทึมและความซับซ้อน คืออะไร

อัลกอริทึมสองแบบอาจแก้ปัญหาเดียวกันแต่ใช้เวลาต่างกันมาก ความซับซ้อนอธิบายว่างานที่ต้องทำเพิ่มขึ้นอย่างไรเมื่ออินพุตใหญ่ขึ้น

ขนาดของอินพุตเรียกว่า n คือจำนวนรายการที่ต้องเรียงลำดับ ความยาวของรายการ หรือจำนวนโหนดในกราฟ

จะเรียน อัลกอริทึมและความซับซ้อน ทีละขั้นได้อย่างไร
  1. ความซับซ้อนวัดอะไร
  2. บิ๊กโอและกลุ่มอัตราการเติบโต
  3. การค้นหา การเรียงลำดับ และการเรียกซ้ำ
  4. วิธีทำทีละขั้น
  5. ตัวอย่างที่แก้ให้ดู
  6. ข้อผิดพลาดที่พบบ่อย
  7. ข้อสอบมีหน้าตาอย่างไร
แบบฝึกหัด อัลกอริทึมและความซับซ้อน ครอบคลุมเรื่องอะไรบ้าง
  • ง่าย: ศัพท์สำคัญและข้อเท็จจริง
  • ปานกลาง: การประยุกต์ใช้แนวคิด
  • ยาก: กรณีศึกษาและการวิเคราะห์

ทุกคำถามมีสี่ตัวเลือก และถูกเพียงข้อเดียว ติดขัดใช่ไหม เปิดคำใบ้เล็ก ๆ ก่อน และเปิดคำอธิบายฉบับเต็มเมื่อจำเป็นเท่านั้น

การฝึกทำงานอย่างไร

  • ทุกคำถามมีสี่ตัวเลือก และถูกเพียงข้อเดียว
  • ติดขัดใช่ไหม เปิดคำใบ้เล็ก ๆ ก่อน และเปิดคำอธิบายฉบับเต็มเมื่อจำเป็นเท่านั้น
  • ความก้าวหน้า ข้อที่ผิด และโจทย์ที่บันทึกไว้จะถูกเก็บไว้ เพื่อให้คุณทบทวนก่อนสอบได้

หัวข้อก่อนและหลังหัวข้อนี้

เรียนต่อด้วย

โครงสร้างข้อมูล

รายวิชาที่มีหัวข้อนี้

โครงสร้างข้อมูลและอัลกอริทึมพื้นฐานวิทยาการคอมพิวเตอร์

หัวข้ออื่นในวิทยาการคอมพิวเตอร์

ระบบเลขการแบ่งซับเน็ต IPv4เครือข่ายคอมพิวเตอร์โครงสร้างข้อมูลฐานข้อมูลและ SQL

ใบงานสำหรับพิมพ์

ใบงาน อัลกอริทึมและความซับซ้อน พร้อมเฉลย
ฝึก อัลกอริทึมและความซับซ้อน ฟรีฝึก อัลกอริทึมและความซับซ้อน เลยโจทย์ฟรีวันละ 5 ข้อ ไม่ต้องใช้บัตร