แผนการเรียน
/

โครงสร้างข้อมูลและอัลกอริทึม
หัวใจของการแก้โจทย์ระดับสากล

วันที่ 2 ช่วงเช้า: การวิเคราะห์ความซับซ้อน (Complexity Analysis)

วัตถุประสงค์การเรียนรู้

1
เข้าใจการวัดประสิทธิภาพอัลกอริทึมด้วย Time Complexity [1, 2]
2
ประมาณการความเร็วของโค้ดเทียบกับข้อจำกัดของเวลา (Time Limit) [3, 4]
3
วิเคราะห์ Big O ของโค้ดในรูปแบบต่าง ๆ ได้อย่างถูกต้อง [5, 6]

ความท้าทายใน Competitive Programming

"การออกแบบอัลกอริทึมที่แค่ทำงานได้ถูกต้องนั้นง่าย แต่ความท้าทายที่แท้จริงคือการสร้างอัลกอริทึมที่ ทำงานได้รวดเร็ว ภายใต้ข้อจำกัด" [1, 7]

  • หากอัลกอริทึมช้าเกินไป จะได้เพียงคะแนนบางส่วน (Partial Points) หรือไม่ได้คะแนนเลย [1, 2]
  • การวิเคราะห์ความซับซ้อนช่วยให้เราตรวจสอบความเร็วได้ ก่อนที่จะเริ่มเขียนโค้ดจริง [5, 6]

นิยามของ Time Complexity

"การประมาณการว่าอัลกอริทึมจะใช้เวลาทำงานเท่าใด โดยมองเป็นฟังก์ชันของ ขนาดของข้อมูลนำเข้า (Input Size: n)" [5, 6]

ตัวอย่าง Input Size (n)

• ขนาดของ Array [5, 6]
• ความยาวของ String [5, 6]
• จำนวน Node ใน Graph [8]

สัญลักษณ์

นิยมใช้ Big O Notation เช่น \(O(n)\), \(O(n^2)\) เพื่อบอกอันดับความเร็ว (Order of Magnitude) [5, 6]

กฎการคำนวณ (Calculation Rules)

1. ละทิ้งค่าคงที่ (Ignore Constants)

Big O สนใจเพียงแนวโน้มการเติบโต ดังนั้น \(3n\), \(n+5\), หรือ \(n/2\) จะถูกนับเป็น \(O(n)\) ทั้งหมด [9, 10]

2. สนใจตัวแปรที่ใหญ่ที่สุด (Dominant Term)

หากมีหลายขั้นตอน ให้นับขั้นตอนที่ช้าที่สุดเป็นตัวกำหนด เช่น \(O(n) + O(n^2) \rightarrow O(n^2)\) [11, 12]

ตัวอย่าง: Single Loop

for (int i = 0; i < n; i++) {
  // some \(O(1)\) operations
}

Complexity: \(O(n)\)

คำอธิบาย: โค้ดภายในลูปทำงาน \(n\) ครั้งตามขนาดข้อมูล [9, 10]

ตัวอย่าง: Double Nested Loop

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    // some \(O(1)\) operations
  }
}

Complexity: \(O(n^2)\)

คำอธิบาย: หากมีลูปซ้อนกัน \(k\) ชั้น ความซับซ้อนจะเป็น \(O(n^k)\) [9, 10]

เมื่อมีหลายขั้นตอนทำงานต่อกัน

Phase 1: \(O(n)\) loop
Phase 2: \(O(n^2)\) nested loops
Phase 3: \(O(n)\) loop

Total Complexity: \(O(n^2)\)

เหตุผล: ขั้นตอนที่ช้าที่สุดคือ Bottleneck ของโปรแกรม [11, 12]

Complexity in Recursion

ขึ้นอยู่กับ จำนวนครั้งที่เรียกฟังก์ชัน \(\times\) ความซับซ้อนของการเรียก 1 ครั้ง [13, 14]

void f(int n) {
  if (n == 1) return;
  f(n-1);
}
\(\rightarrow O(n)\) [15, 16]
void g(int n) {
  if (n == 1) return;
  g(n-1); g(n-1);
}
\(\rightarrow O(2^n)\) [17, 18]

ตารางเปรียบเทียบความเร็ว

Big O นิยาม ตัวอย่าง
\(O(1)\)Constant Timeการคำนวณสูตรคณิตศาสตร์ [17, 19]
\(O(\log n)\)LogarithmicBinary Search [17, 19]
\(O(n)\)Linearวนลูป 1 รอบ [20, 21]
\(O(n \log n)\)SortingEfficient Sorting (เช่น sort) [20, 21]
\(O(n^2)\)QuadraticNested loops [22, 23]

Logarithm: พลังของการ "แบ่งครึ่ง"

\(O(\log n)\) มักเกิดขึ้นเมื่ออัลกอริทึม ลดขนาดข้อมูลลงครึ่งหนึ่ง ในแต่ละขั้นตอน [17, 19]
\(32 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1\)
ใช้เพียง 5 ขั้นตอนสำหรับข้อมูลขนาด 32! [24]

หมายเหตุ: ในการวิเคราะห์อัลกอริทึม ฐานของ Logarithm มักจะเป็น 2 [24]

Rule of Thumb

10^8

การดำเนินการต่อวินาที

คอมพิวเตอร์สมัยใหม่สามารถประมวลผลได้ประมาณ 100 ล้านครั้งต่อวินาที [3, 4, 25, 26]
นี่คือจุดตัดสินว่าโค้ดของคุณจะ Accepted หรือ TLE!

เดาทางโจทย์จากขอบเขตข้อมูล (1 วินาที)

\(n \le 10\) \(O(n!)\) [27-29]
\(n \le 20\) \(O(2^n)\) [27-29]
\(n \le 500\) \(O(n^3)\) [27-29]
\(n \le 5000\) \(O(n^2)\) [27-29]
\(n \le 10^6\) \(O(n \log n)\) หรือ \(O(n)\) [27-29]
\(n\) ขนาดใหญ่มาก \(O(\log n)\) หรือ \(O(1)\) [27-29]

Space Complexity

นอกจากเวลาแล้ว เรายังต้องคำนึงถึง หน่วยความจำ ที่ใช้อีกด้วย โดยใช้ Big O Notation เช่นเดียวกัน [30]

ตัวอย่าง:

  • Array 1 มิติ ขนาด \(n\) \(\rightarrow O(n)\)
  • Array 2 มิติ ขนาด \(n \times n\) \(\rightarrow O(n^2)\)
"หาก Memory Limit เกิน โจทย์มักจะ Time Limit เกินด้วย" [30]

ทำไมโค้ด \(O(n)\) ถึงช้ากว่ากัน?

Big O ละทิ้ง ค่าคงที่ (Constant Factors) [31-33]

\(0.5n\)
\(5n\)
\(100n\)

ทั้ง 3 ตัวคือ \(O(n)\) แต่ในโลกของ CP ค่าคงที่ที่ซ่อนอยู่ส่งผลต่อ Wall-clock time จริง! [33]

Case Study

โจทย์เดียวกัน แต่อัลกอริทึมต่างกัน ผลลัพธ์ต่างกันมหาศาล! [31, 32]

ปัญหา: หาผลรวมที่มากที่สุดของ Subarray ต่อเนื่อง

Example: [-1, 2, 4, -3, 5, 2, -5, 2] \(\rightarrow\) Max is 10

อัลกอริทึม 1: วนลูป 3 ชั้น [34, 35]

for (int i = 0; i < n; i++) {
  for (int j = i; j < n; j++) {
    int sum = 0;
    for (int k = i; k <= j; k++) sum += arr[k];
    best = max(best, sum);
  }
}
Time Complexity: \(O(n^3)\)
รับได้เพียง \(n \approx 500\) ภายใน 1 วินาที! [27, 28]

อัลกอริทึม 2: ตัดลูปที่ไม่จำเป็น [34, 35]

for (int i = 0; i < n; i++) {
  int sum = 0;
  for (int j = i; j < n; j++) {
    sum += arr[j];
    best = max(best, sum);
  }
}
Time Complexity: \(O(n^2)\)
รับได้ \(n \approx 5000\) ภายใน 1 วินาที! [27, 28]

อัลกอริทึม 3: คิดแบบอัจฉริยะ (DP) [36, 37]

for (int i = 0; i < n; i++) {
  sum = max(arr[i], sum + arr[i]);
  best = max(best, sum);
}
Time Complexity: \(O(n)\)
รับได้ \(n \ge 10^7\) ได้อย่างสบาย! ทรงพลังที่สุด [38, 39]

Efficiency Comparison

n
\(O(n^3)\)
\(O(n^2)\)
\(O(n)\)
\(10^2\)
0.0 s
0.0 s
0.0 s
\(10^4\)
>10.0 s
0.1 s
0.0 s
\(10^6\)
ช้ามาก
>10.0 s
0.0 s

ผลลัพธ์จากการทดสอบบนคอมพิวเตอร์สมัยใหม่ [38, 39]

Next Topic...

เมื่อ \(O(n)\) ยังเร็วไม่พอ...

Binary Search

เปลี่ยนจาก Linear (\(O(n)\)) เป็น Logarithmic (\(O(\log n)\)) [26]

พัก 15 นาที ก่อนเข้าสู่หัวใจของการค้นหา

Binary Search
พลังของการแบ่งครึ่งเพื่อคำตอบ

การค้นหาประสิทธิภาพสูงจาก \(O(n)\) สู่ \(O(\log n)\) และการประยุกต์ใช้หาคำตอบขั้นสูง [1]

หัวข้อที่จะเรียนรู้

1
พื้นฐานและเงื่อนไขการใช้ Binary Search
2
การเขียนโค้ดแบบมาตรฐาน (Iterative & Jump Search)
3
Binary Search on Answer: เทคนิคเปลี่ยนโจทย์ยากให้เป็นโจทย์ง่าย

ทำไมต้อง Binary Search?

Linear Search

  • • ตรวจสอบทีละตัวตั้งแต่ต้นจนจบ
  • • ใช้ได้กับข้อมูลทุกรูปแบบ
  • • Complexity: \(O(n)\)
  • "เหมือนเปิดพจนานุกรมทีละหน้า"

Binary Search

  • • ตัดข้อมูลที่ไม่เกี่ยวข้องออกทีละ "ครึ่งหนึ่ง" [1]
  • • ข้อมูล ต้องเรียงลำดับ (Sorted) เท่านั้น [1, 2]
  • • Complexity: \(O(\log n)\)
  • "เหมือนเปิดพจนานุกรมแบบสุ่มกลางเล่ม"

The Pre-requisite

"The array must be SORTED!"

หากข้อมูลยังไม่เรียงลำดับ การทำ Binary Search จะให้คำตอบที่ ผิดพลาด [1, 3]
ดังนั้นในหลายโจทย์ เรามักต้อง std::sort ก่อนทำ Binary Search [4, 5]

How it works? (Method 1)

1 กำหนดขอบเขตการค้นหาเริ่มต้น low = 0, high = n-1 [6]
2 หาจุดกึ่งกลาง mid = (low + high) / 2 [6]
3 ถ้า arr[mid] == target หยุดการค้นหา [6]
4 ถ้า arr[mid] > target ให้หาต่อในครึ่ง "ซ้าย" (เลื่อน high) [6]
5 ถ้า arr[mid] < target ให้หาต่อในครึ่ง "ขวา" (เลื่อน low) [6]

Iterative Binary Search

int low = 0, high = n - 1;
while (low <= high) {
  int mid = low + (high - low) / 2;
  if (array[mid] == x) return mid;
  if (array[mid] > x) high = mid - 1;
  else low = mid + 1;
}
return -1; // Not found

*หมายเหตุ: การใช้ low + (high - low) / 2 ช่วยป้องกันปัญหา Integer Overflow [7, 8]

The "Jump" Strategy

อีกหนึ่งวิธีในการมอง Binary Search คือการ "กระโดด" ไปข้างหน้าด้วยขนาดที่ลดลงทีละครึ่ง [9, 10]

Step 1

Jump n/2

Step 2

Jump n/4

Step n

Jump 1

วิธีนี้ได้รับความนิยมมากในหมู่นักแข่งระดับโลก เพราะเขียนโค้ดได้กระชับและลดความผิดพลาดเรื่อง boundaries [11]

Jump-based Implementation

int k = 0;
for (int b = n/2; b >= 1; b /= 2) {
  while (k+b < n && array[k+b] <= x) k += b;
}
if (array[k] == x) {
  /* found at index k */
}
ความซับซ้อน: ยังคงเป็น \(O(\log n)\) เพราะการวนลูป while จะทำงานสูงสุดไม่เกิน 2 ครั้งต่อหนึ่งขนาดการกระโดด [12, 13]

C++ STL Powerhouse

ไม่ต้องเขียนเองเสมอไป! C++ มีฟังก์ชันที่ปรับแต่งมาอย่างดีแล้ว [12, 14]

binary_search()

คืนค่าเป็น boolean (true/false) ว่ามีข้อมูลอยู่ในช่วงที่ระบุหรือไม่ [14]

lower_bound()

คืนค่า iterator ไปยังตัวแรกที่ "ไม่น้อยกว่า" (>=) x [15, 16]

upper_bound()

คืนค่า iterator ไปยังตัวแรกที่ "มากกว่า" (>) x [15, 16]

equal_range()

คืนค่าทั้งขอบเขตบนและล่างพร้อมกัน (เป็น pair) [15, 16]

STL Code Snippet

vector<int> v = {1, 3, 3, 5, 7, 8, 9};
// ค้นหาเลข 3 ตัวแรก (>= 3)
auto it1 = lower_bound(v.begin(), v.end(), 3);

// ค้นหาตัวแรกที่มากกว่า 3 (> 3)
auto it2 = upper_bound(v.begin(), v.end(), 3);

// นับจำนวนเลข 3 ใน Array
cout << it2 - it1 << endl; // Output: 2

จุดเปลี่ยนสำคัญ

"จะเกิดอะไรขึ้น... หากสิ่งที่เราต้องการค้นหาไม่ใช่ตำแหน่งข้อมูลใน Array
แต่คือ 'คำตอบ' ของโจทย์ที่เราคำนวณโดยตรงไม่ได้?"

Binary Search on Answer

นิยามการค้นหาบนคำตอบ

"เมื่อเราไม่สามารถคำนวณคำตอบโดยตรงได้ แต่เราสามารถ ตรวจสอบ (Check) ได้ว่าค่านี้ 'ใช้ได้' หรือไม่" [7, 17]

เราจะสุ่มเดาคำตอบ (x) และใช้ฟังก์ชัน bool ok(x) เพื่อดูว่าคำตอบนั้นเป็นไปได้ไหม
แล้วใช้ Binary Search ค่อยๆ บีบขอบเขตเพื่อหาค่า x ที่ดีที่สุด [18, 19]

หัวใจ: Monotonic Function

โจทย์ที่จะทำ Binary Search on Answer ได้ ต้องมีคำตอบที่ต่อเนื่องกันแบบนี้: [18, 20]

F, F, F, F, T, T, T, T

(F = ใช้ไม่ได้, T = ใช้ได้)
เมื่อมันเปลี่ยนจาก F เป็น T แล้ว ต้องเป็น T ไปตลอด (หรือสลับกัน) [21, 22]

boolean ok(long long x)

bool ok(long long x) {
  // ตรวจสอบว่า x เป็นคำตอบที่เป็นไปได้หรือไม่
  // มักใช้อัลกอริทึม \(O(n)\) หรือ Greedy มาช่วย
  if (condition_met) return true;
  return false;
}
Complexity: ถ้า ok(x) ทำงานใน \(O(n)\) เวลาทั้งหมดจะเป็น \(O(n \log z)\) [21, 22]

กรณีศึกษา: การตัดไส้กรอก

ปัญหา:

มีไส้กรอก \(N\) ชิ้นยาวต่างกัน ต้องการตัดไส้กรอกให้ผู้เข้าแข่ง \(M\) คน โดยทุกคนต้องได้ยาวเท่ากัน (ยาว \(L\)) ถามว่า \(L\) ที่ยาวที่สุดที่เป็นไปได้คือเท่าไหร่? [23]

  • Inversion: แทนที่จะหา L ตรงๆ ให้ถามว่า "ถ้าตัดยาว x จะเลี้ยงคนได้ถึง M คนไหม?" [24]
  • Logic: ถ้ายาว x ใช้ได้ ยาว x-1 ก็ย่อมใช้ได้ (Monotonic!) [24]

Finding the Smallest Solution

long long x = -1;
for (long long b = max_possible; b >= 1; b /= 2) {
  while (!ok(x + b)) x += b;
}
long long k = x + 1; // k คือค่าที่น้อยที่สุดที่ทำให้ ok(k) เป็นจริง [20]

วิธีนี้ใช้ Jump Strategy เพื่อหาจุดเปลี่ยนจาก False เป็น True ได้อย่างแม่นยำ [20, 25]

เมื่อคำตอบเป็น "ทศนิยม"

ในโจทย์พิกัดหรือเรขาคณิต เราต้องใช้ Binary Search กับจำนวนจริง (double/long double) [26]

Option 1: Precision

while (hi - lo > 1e-9)

ระวัง: อาจเกิด Infinite Loop ถ้ากำหนดละเอียดเกินขีดจำกัดของ double [27]

Option 2: Fixed Iterations

for (int i=0; i<100; i++)

แนะนำ: การวนลูป 100 ครั้งให้ความละเอียดถึง \(10^{-30}\) และปลอดภัยกว่ามาก [28]

Competitive Tip!

"Double-precision (double) มีความละเอียดเพียงประมาณ 15-17 หลัก เท่านั้น" [27]

หากขอบเขตการค้นหาคือ \(10^{12}\) และคุณตั้งความละเอียดที่ \(10^{-7}\)
ความแตกต่างระหว่าง lo และ hi อาจเหลือน้อยเกินกว่าที่คอมพิวเตอร์จะเก็บได้! [27]

กับดัก: เลขเกินความจุ

int mid = (low + high) / 2;
// หาก low และ high มีค่าใกล้ \(2 \cdot 10^9\)
// การบวกกันจะเกินขีดจำกัดของ int (2.1B)!

วิธีแก้:

  • ใช้ long long ในการคำนวณช่วงเสมอ [29]
  • ใช้สูตร mid = low + (high - low) / 2 เพื่อเลี่ยงการบวกค่ามาก

กับดัก: วนลูปไม่รู้จบ

ปัญหาพบบ่อยที่สุดคือการจัดการ low และ high ที่ไม่สอดคล้องกับเงื่อนไขการหยุด [8]

ผิด:

while (low < high) {
  int mid = (low+high)/2;
  if (ok(mid)) low = mid;
  else high = mid;
}

ถูก (Best Practice):

while (low <= high) {
  ...
  low = mid + 1;
  high = mid - 1;
}

"จงชัดเจนกับขอบเขต (Inclusive vs Exclusive) เสมอ" [8]

Test Your Understanding

ถ้าข้อมูลมีขนาด \(10^9\) ตัว
Binary Search จะใช้เวลาตรวจสอบสูงสุดกี่ครั้ง?

1,000,000,000
~30
~1,000

คำใบ้: \(2^{10} \approx 10^3, 2^{20} \approx 10^6, 2^{30} \approx 10^9\)

Binary Search ในสนามจริง

1. Minimum of Maximum (Minimax):

หาค่าที่น้อยที่สุดของค่าสูงสุดที่เป็นไปได้ (เช่น โจทย์แบ่งงานให้คนทำงานพร้อมกัน)

2. Maximum of Minimum (Maximin):

หาค่าที่มากที่สุดของค่าต่ำสุดที่เป็นไปได้ (เช่น โจทย์วางเสาสัญญาณให้ห่างกันที่สุด)

3. Finding Invariants:

ใช้พิสูจน์ความถูกต้องของ Greedy หรืออธิบายพฤติกรรมของระบบ [30]

กลยุทธ์การทำ Subtasks

จำไว้เสมอ:

ในโจทย์โอลิมปิก (IOI Style) หลายข้อ อัลกอริทึม \(O(n^2)\) หรือ \(O(n^3)\) อาจได้คะแนนเพียง 20-30 แต้ม
แต่การเพิ่ม Binary Search เข้าไปเพียงเล็กน้อย มักจะช่วยขยับคะแนนขึ้นไปถึง 50-70 แต้มได้ทันที! [31]

Take-home Message

Do...

  • ✅ ตรวจสอบว่าข้อมูลเรียงลำดับแล้ว
  • ✅ ระวัง Integer Overflow ใน mid
  • ✅ ใช้ long long เมื่อค่าเกิน \(10^9\)
  • ✅ ใช้ Fixed 100 loops กับทศนิยม

Don't...

  • ❌ อย่าทำ Binary Search บนข้อมูลสุ่ม
  • ❌ อย่าลืม it1 - v.begin() เมื่อใช้ STL
  • ❌ อย่าปล่อยให้ low ติดที่ค่าเดิมจนวนลูปไม่จบ
  • ❌ อย่ามองข้ามการทำ BS on Answer

Where to Practice?

CSES

Sorting & Searching section (Highly Recommended) [7]

Codeforces

Tag: 'binary search'
(Rating 800-1400) [7]

USACO Guide

Silver level: Binary Search on Answer [7]

Time to Code!

13.00 - 15.00 น.

Binary Search Implementation on Arrays & Answers

เตรียมเครื่องให้พร้อม เจอกันในช่วงบ่ายครับ!