Big O Notation: What A-Level CS Actually Expects

Big O notation ปรากฏในทุกข้อกำหนด A-level computer science หลัก (AQA, OCR, Edexcel) และมันทำให้นักเรียนจำนวนมากติดขัดไม่ใช่เพราะคณิตศาสตร์ยาก แต่เพราะพวกเขาไม่เคยเห็นมันเชื่อมต่อกับโค้ดที่แท้จริง นี่คือการอธิบายปฏิบัติสิ่งที่คุณต้องรู้และวิธีตอบคำถามสอบเกี่ยวกับมันโดยไม่พูดลอยๆ

Big O วัดอะไรจริงๆ

Big O อธิบายวิธีการที่เวลาในการทำงาน (หรือการใช้หน่วยความจำ) ของอัลกอริทึมเติบโตตามขนาดของอินพุต โดยปกติเรียกว่า n เมื่อมันใหญ่ขึ้น มันไม่ได้เป็นการวัดที่หยุดนาฬิกาเป็นวินาที มันเป็นวิธีการอธิบายอัตราการเติบโตเพื่อให้คุณสามารถเปรียบเทียบอัลกอริทึมได้โดยไม่ขึ้นกับฮาร์ดแวร์

เมื่อคุณเขียน O(n) คุณกำลังพูดว่า: หากฉันเพิ่มอินพุตเป็นสองเท่า งานจะเพิ่มขึ้นประมาณสองเท่า O(n²) หมายความว่าการเพิ่มอินพุตเป็นสองเท่าจะทำให้งานเพิ่มขึ้นประมาณสี่เท่า ความสัมพันธ์นั้นคือสิ่งที่ผู้ทดสอบต้องการให้คุณระบุ ไม่ใช่การนับการดำเนินการที่แน่นอน

ความซับซ้อนที่คุณต้องรู้ให้ดี

สำหรับ A-level สิ่งเหล่านี้คือสิ่งที่ปรากฏซ้ำแล้วซ้ำอีก:

• O(1) – เวลาคงที่ การเข้าถึงองค์ประกอบอาร์เรย์ตามดัชนี: arr[5] ไม่สำคัญว่าอาร์เรย์จะใหญ่แค่ไหน
• O(log n) – ลอการิทึม การค้นหาแบบไบนารีในรายการที่จัดเรียง แต่ละขั้นตอนลดพื้นที่การค้นหาที่เหลือลงครึ่งหนึ่ง
• O(n) – เชิงเส้น วนซ้ำเดี่ยวผ่านรายการ เช่นการค้นหาเชิงเส้นที่ตรวจสอบแต่ละรายการหนึ่งครั้ง
• O(n log n) – linearithmic Merge sort และ quicksort (average case) อยู่ที่นี่
• O(n²) – กำลังสอง วนซ้ำแบบซ้อนกันบนข้อมูลเดียวกัน ซึ่งเป็นสิ่งที่ bubble sort, insertion sort และ selection sort ทำ
• O(2ⁿ) – เลขชี้กำลัง Fibonacci แบบวนซ้ำไร้เดียวกรรมโดยไม่ใช้ memoisation มันยุ่งเหยิงอย่างรวดเร็ว

คุณควรสามารถดูรหัสเทียมและบอกได้ว่ามันคืออันไหนในสิ่งเหล่านี้เมื่อมองเห็นเพราะนั่นคือสิ่งที่ได้รับการทดสอบส่วนใหญ่

การอ่านโค้ดสำหรับความซับซ้อน

วิธีการที่ใช้ได้ทุกครั้ง: นับลูปและดูว่าพวกมันเกี่ยวข้องกับ n อย่างไร

# O(n) - one loop, one pass
for i in range(n):
    print(i)

# O(n^2) - nested loop, both tied to n
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - the search space halves each iteration
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

ลูปแบบซ้อนที่ช่วงของลูปด้านในขึ้นอยู่กับ n ยังคงเป็น O(n²) แม้ว่ามันจะดูแตกต่างกันเล็กน้อย (เช่น for j in range(i) แทนที่จะเป็น for j in range(n) — มันยังคงเป็นกำลังสองโดยรวม มีเพียงความแตกต่างของปัจจัยค่าคงที่)

ระวังลูปที่ไม่ขึ้นกับ n เลย ลูปที่ทำงาน 10 ครั้งเสมอโดยไม่คำนึงถึงขนาดอินพุตคือ O(1) แม้ว่าจะมีลูปอยู่ก็ตาม ผู้ทดสอบชอบอ่อนไปด้วยสิ่งนี้

อัลกอริทึมการเรียงลำดับทั่วไปและ Big O ของพวกมัน

นี่คือหัวข้อสอบโปรดเพราะมันรวมข้อกำหนดสองข้อพร้อมกัน: อัลกอริทึมการเรียงลำดับและความซับซ้อน

Algorithm	Best case	Worst case
Bubble sort	O(n)	O(n²)
Insertion sort	O(n)	O(n²)
Merge sort	O(n log n)	O(n log n)
Binary search	O(1)	O(log n)
Linear search	O(1)	O(n)

ความสม่ำเสมอของ Merge sort (ความซับซ้อนเดียวกันที่ดีที่สุดและกรณีที่เลวร้ายที่สุด) คุ้มค่าที่จะกล่าวถึงอย่างชัดแจ้งหากคำถามถามว่าเหตุใดคุณจึงจะเลือกมันแทน bubble sort สำหรับชุดข้อมูลขนาดใหญ่ กรณีที่ดีที่สุดของ Bubble sort O(n) ใช้ได้เฉพาะกับการเพิ่มประสิทธิ์การออกจากเร็วเมื่อไม่มีสวิตช์เกิดขึ้นในการผ่าน — กล่าวถึงรายละเอียดนั้นหากคุณนำมันขึ้นมา เนื่องจากบอร์ดสอบบางแห่งคาดหวังมัน

ที่ที่นักเรียนสูญเสียคะแนน

รายหนึ่งที่ใหญ่ที่สุด: การเขียน