Time & Space Complexity

การวิเคราะห์ Complexity เป็นทักษะสำคัญที่สุดในการแข่งขัน Competitive Programming เพราะช่วยให้เราประเมินได้ว่า Algorithm ของเราจะรันทันเวลาหรือไม่

Big O Notation คืออะไร?

Big O Notation เป็นวิธีการอธิบายว่า Algorithm ทำงานช้าลงเท่าไหร่เมื่อขนาดของ input เพิ่มขึ้น

ตัวอย่างการวิเคราะห์

// O(1) - Constant Time
int getFirst(vector<int>& arr) {
    return arr[0];
}

// O(n) - Linear Time
int sum(vector<int>& arr) {
    int total = 0;
    for (int x : arr) total += x;
    return total;
}

// O(n²) - Quadratic Time
void printPairs(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << arr[i] << " " << arr[j] << endl;
        }
    }
}

Common Time Complexities

เรียงจากเร็วที่สุดไปช้าที่สุด:

Complexity	ชื่อ	ตัวอย่าง
$O(1)$	Constant	Array access, Hash table
$O(\log n)$	Logarithmic	Binary Search
$O(\sqrt{n})$	Square Root	Prime factorization
$O(n)$	Linear	Linear Search, ไล่ loop
$O(n \log n)$	Linearithmic	Merge Sort, Sort
$O(n^2)$	Quadratic	Bubble Sort, 2 nested loops
$O(n^3)$	Cubic	Matrix multiplication
$O(2^n)$	Exponential	Subset generation
$O(n!)$	Factorial	Permutation

การประมาณจำนวน Operations

กฎง่ายๆ: คอมพิวเตอร์ทำได้ประมาณ $10^8$ operations ต่อวินาที

ตารางอ้างอิง

ขนาด n	Complexity ที่ยอมรับได้
$n \leq 10$	$O(n!)$, $O(n^7)$
$n \leq 20$	$O(2^n)$, $O(n^5)$
$n \leq 100$	$O(n^4)$
$n \leq 500$	$O(n^3)$
$n \leq 5000$	$O(n^2)$
$n \leq 10^5$	$O(n \log n)$
$n \leq 10^6$	$O(n)$
$n \leq 10^8$	$O(\log n)$, $O(1)$

ตัวอย่างการวิเคราะห์

ตัวอย่าง 1: Two Sum

// วิธีที่ 1: Brute Force O(n²)
vector<int> twoSumBrute(vector<int>& nums, int target) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] == target) {
                return {i, j};
            }
        }
    }
    return {};
}

// วิธีที่ 2: Hash Map O(n)
vector<int> twoSumOptimal(vector<int>& nums, int target) {
    unordered_map<int, int> seen;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (seen.count(complement)) {
            return {seen[complement], i};
        }
        seen[nums[i]] = i;
    }
    return {};
}

การวิเคราะห์:

• ถ้า $n = 10^5$:
  • วิธีที่ 1: $10^{10}$ operations → TLE (Time Limit Exceeded)
  • วิธีที่ 2: $10^5$ operations → ผ่าน

ตัวอย่าง 2: Binary Search

// O(log n) - หาตำแหน่งของ target ใน sorted array
int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1; // ไม่พบ
}

ทำไมถึงเป็น $O(\log n)$?

• ทุกครั้งที่วน loop ขนาดของ search space ลดลงครึ่งหนึ่ง
• ถ้า $n = 10^6$: ต้องวนแค่ประมาณ $\log_2(10^6) \approx 20$ ครั้ง

Space Complexity

นอกจาก Time Complexity แล้ว ต้องคำนึงถึง Memory ด้วย

// O(1) Space - ไม่ใช้ memory เพิ่มเติม
void reverseInPlace(vector<int>& arr) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        swap(arr[left++], arr[right--]);
    }
}

// O(n) Space - ใช้ memory เพิ่มตาม input size
vector<int> copyReverse(vector<int>& arr) {
    vector<int> result(arr.rbegin(), arr.rend());
    return result;
}

Memory Limits ที่พบบ่อย

Limit	สิ่งที่เก็บได้
256 MB	int array ขนาด ~$6 \times 10^7$
256 MB	long long array ขนาด ~$3 \times 10^7$
256 MB	2D int array ขนาด ~$8000 \times 8000$

Common Mistakes

1. Hidden Complexity ใน STL

// ❌ ไม่ดี - O(n) per insertion
vector<int> v;
for (int i = 0; i < n; i++) {
    v.insert(v.begin(), i); // insert ที่ต้นใช้ O(n)
}
// รวมเป็น O(n²)

// ✅ ดีกว่า - O(1) per insertion
deque<int> d;
for (int i = 0; i < n; i++) {
    d.push_front(i); // O(1)
}
// รวมเป็น O(n)

2. String Concatenation

// ❌ ไม่ดี - O(n²) เพราะ string copy
string result = "";
for (int i = 0; i < n; i++) {
    result += to_string(i);
}

// ✅ ดีกว่า - O(n)
stringstream ss;
for (int i = 0; i < n; i++) {
    ss << i;
}
string result = ss.str();

3. การส่ง Parameter

// ❌ ไม่ดี - copy ทั้ง vector ทุกครั้ง
int solve(vector<int> arr) { ... }

// ✅ ดีกว่า - ส่ง reference
int solve(vector<int>& arr) { ... }
int solve(const vector<int>& arr) { ... }

สรุป

1. วิเคราะห์ก่อนเขียน - ประเมิน complexity ก่อนลงมือ code
2. จำตารางอ้างอิง - รู้ว่าขนาด input เท่าไหร่ใช้ complexity อะไรได้
3. ระวัง Hidden Cost - STL บางอย่างมี complexity ซ่อนอยู่
4. ฝึกวิเคราะห์ - ยิ่งวิเคราะห์บ่อยยิ่งเก่ง

💡 Tip: ถ้าไม่แน่ใจ ให้คำนวณจำนวน operations จริงๆ แล้วหารด้วย $10^8$ จะได้เวลาโดยประมาณ