คำถามน่าสนใจเกี่ยวกับ Time Complexity ใน C++

Time Complexity คืออะไร?

เวลาที่อัลกอริทึมใช้ในการรัน แสดงเป็นฟังก์ชันของขนาด input (n) โดยใช้ Big-O notation

ตัวอย่างที่ 1: Nested Loop แบบพิเศษ

void counter(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j += i) {
            cout << i << " " << j << endl;
        }
    }
}

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

• i=1: inner loop รัน n ครั้ง (j=1,2,3...n)
• i=2: inner loop รัน n/2 ครั้ง (j=1,3,5...)
• i=3: inner loop รัน n/3 ครั้ง
• ...
• i=n: inner loop รัน 1 ครั้ง

รวม operations = n/1 + n/2 + n/3 + ... + n/n = n(1 + 1/2 + 1/3 + ... + 1/n)

อนุกรม Harmonic: Hₙ ≈ ln(n) + γ → O(n log n)

ตัวอย่างที่ 2: Loop ภายในขึ้นกับ log

void counter(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= log(i); j++) {
            cout << i << " " << j << endl;
        }
    }
}

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

รวม = log(1) + log(2) + log(3) + ... + log(n) = log(n!)

ใช้ Stirling's approximation: log(n!) ≈ n log n - n + O(log n) → O(n log n)

สรุปเทคนิคการวิเคราะห์

เคล็ดลับ

• นับจำนวน iteration ของ inner loop ต่อแต่ละ outer loop
• รวมเป็น sigma notation แล้วหาอนุกรม
• Harmonic series Hₙ = Θ(log n)
• log(n!) = Θ(n log n)