Time complexity ช่วยเห็นว่า ทำไมอัลกอริทึม/โปรแกรมจึงช้า และแก้ไขอย่างไร ไม่ต้องมี degree CS ก็เข้าใจได้
Slow vs Fast
ไม่ได้ถามว่า 150ms ช้าหรือเร็ว แต่ถามว่า เมื่อ input size เพิ่มขึ้น performance จะเปลี่ยนอย่างไร Input size = ขนาดอาร์กิวเมนต์ (ความยาว string, ขนาด array)
Big O Notation
จัดกลุ่มอัลกอริทึมตาม performance:
| Notation | Name | Description |
|---|---|---|
| O(1) | Constant | ใช้เวลาเท่ากันเสมอ |
| O(log n) | Logarithmic | งานลดลงครึ่งทีแต่ละรอบ (binary search) |
| O(n) | Linear | เวลาเพิ่มขึ้นสัดส่วน 1:1 กับ input size |
| O(n log n) | Linearithmic | Nested loop inner loop เป็น log n (quicksort, mergesort, heapsort) |
| O(n^2) | Quadratic | Nested loop ทั้งคู่นอกและคู่นใน loop ทุก element |
| O(n^3) | Cubic | Triple nested loop |
| O(2^n) | Exponential | ช้ามากกว่า n^2 มาก (recursive fibonacci) |
Algorithm Analysis
คิด input เป็น array n elements หาเลขคู่ต้องอ่านทุกตัว → O(n)
[1,2,3,4,5,6,7,8,9,10].select(&:even?)
3 Different Solutions To The Same Problem
Scrabble checker: ตัวอักษร ollhe → คำ hello
Solution 1: count method
def scramble(characters, word)
word.each_char.all? { |c| characters.count(c) >= word.count(c) }
end
count loop ทุกตัว → O(n^2)
Solution 2: sub! remove characters
def scramble(characters, word)
characters = characters.dup
word.each_char.all? { |c| characters.sub!(c, "") }
end
Best case เร็วกว่า (เจอตัวอักษรต้นแรก) แต่ worst case ยัง O(n^2)
Solution 3: Hash table
def scramble(characters, word)
available = Hash.new(1)
characters.each_char { |c| available[c] += 1 }
word.each_char.all? { |c| available[c] -= 1; available[c] > 0 }
end
Hash read/write = O(1) สอง loop ไม่ nested → O(n)
Benchmark ผลลัพธ์ตรงกับทฤษฎี: hash เร็วที่สุด, sub กลาง, count ช้าที่สุด
Summary
เรียนรู้ Time Complexity, Big O, การวิเคราะห์ และเปรียบเทียบ 3 วิธีแก้ปัญหาเดียวกัน
