18.3 วิเคราะห์ลูปและ recursion

หน้า 18.1 นับจำนวนการทำงานของโปรแกรมเดียวอย่างละเอียด ในการแข่งขันจริงไม่มีเวลานับทีละรอบแบบนั้น ต้องมองโครงของโค้ดแล้วบอก Big O ได้ในไม่กี่วินาที หน้านี้รวมรูปแบบที่เจอบ่อย ได้แก่ลูปซ้อน ลูปที่ตัวแปรคูณสองหรือหารสอง และ recursion แบบง่าย ทุกแบบมีโปรแกรมที่นับรอบจริงให้เทียบกับที่คิด

กฎสามข้อ

1. ทำต่อกัน ให้บวก แล้วเก็บตัวที่ใหญ่ที่สุด อ่านข้อมูล O(N) ตามด้วย sort O(N log N) ตามด้วยลูปไล่ทุกคู่ O(N²) รวมเป็น O(N + N log N + N²) ซึ่งก็คือ O(N²) ส่วนที่ช้าที่สุดเป็นตัวตัดสิน
2. ซ้อนกัน ให้คูณ ลูปนอก N รอบ ทุกรอบมีลูปใน M รอบ รวมเป็น O(NM) เช่น เดินทุกช่องของตาราง R แถว C คอลัมน์ในบทที่ 7 เป็น O(RC)
3. มี if else ให้คิดฝั่งที่แย่กว่า เพราะเราวิเคราะห์กรณีแย่ที่สุด

ลูปซ้อน

โปรแกรมนี้ไม่ได้ทำอะไรนอกจากนับ แต่ละตัวนับแทนลูปหนึ่งแบบ ลองทายผลของแต่ละบรรทัดก่อนดูกล่องผลลัพธ์

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    long long single = 0, square = 0, pairs = 0, letters = 0;
    for (int i = 0; i < n; i++) {
        single++;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            square++;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            pairs++;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            letters++;
        }
    }
    cout << "single = " << single << '\n';
    cout << "square = " << square << '\n';
    cout << "pairs = " << pairs << '\n';
    cout << "letters = " << letters << '\n';
    return 0;
}

1000

single = 1000
square = 1000000
pairs = 499500
letters = 26000

แถวสุดท้ายสำคัญ ลูปซ้อนสองชั้นไม่ได้แปลว่า O(N²) เสมอ ต้องดูว่าลูปในวนกี่รอบ และจำนวนรอบนั้นขึ้นกับ N หรือไม่ ลูปในที่วนตามตัวอักษร 26 ตัว หรือวนดูช่องข้างเคียงไม่กี่ช่องแบบหน้า 7.4 เป็นแค่ค่าคงที่ ถ้ามีลูปสามชั้นที่ทุกชั้นขึ้นกับ N แบบ i < j < k ก็จะนับได้ N(N − 1)(N − 2) / 6 ซึ่งเป็น O(N³)

ตัวแปรคูณสองหรือหารสอง

ลูปที่ตัวแปรเพิ่มทีละหนึ่งวนตามขนาดของ N แต่ลูปที่ตัวแปร คูณสอง ทุกรอบ ไปถึง N เร็วมาก 1 2 4 8 ... ถึง N ใช้ราว log₂ N รอบ ลูปที่ หารสอง ทุกรอบจนเหลือ 0 ก็เหมือนกัน และลูปที่หารสิบอย่างการนับหลักในหน้า 4.5 ใช้ log₁₀ N รอบ ซึ่งก็เป็น O(log N)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    long long doubling = 0, root = 0, nested = 0, harmonic = 0;
    for (int i = 1; i <= n; i *= 2) {
        doubling++;
    }
    for (int i = 1; i * i <= n; i++) {
        root++;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= n; j *= 2) {
            nested++;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            harmonic++;
        }
    }
    cout << "doubling = " << doubling << '\n';
    cout << "root = " << root << '\n';
    cout << "nested = " << nested << '\n';
    cout << "harmonic = " << harmonic << '\n';
    return 0;
}

1000

doubling = 10
root = 31
nested = 10000
harmonic = 7069

• doubling i เป็น 1 2 4 ... 512 รวม 10 ค่า ตัวถัดไปคือ 1024 ซึ่งเกิน 1000 แล้ว 10 รอบคือ log₂ 1000 ปัดลงแล้วบวกหนึ่ง เป็น O(log N)
• root i วิ่งถึง 31 เพราะ 31 × 31 = 961 แต่ 32 × 32 = 1024 เป็น O(√N) แบบการตรวจจำนวนเฉพาะในหน้า 4.5
• nested ลูปนอก N รอบ ลูปในคูณสองทุกรอบ ใช้ 10 รอบ รวม 1000 × 10 ตามกฎข้อ 2 เป็น O(N log N)
• harmonic ลูปในกระโดดทีละ i ตอน i = 1 วน N รอบ ตอน i = 2 วน N/2 รอบ ตอน i = 3 วน N/3 รอบ รวมเป็น N/1 + N/2 + N/3 + ... + N/N ผลบวกนี้ประมาณ N คูณ log ฐาน e ของ N ซึ่ง N = 1000 ได้ราว 6908 ใกล้กับ 7069 ที่นับได้ จึงเป็น O(N log N) ไม่ใช่ O(N²) อย่างที่หน้าตาของลูปซ้อนชวนให้คิด ตะแกรงหาจำนวนเฉพาะในหน้า 12.2 ก็กระโดดแบบนี้

จำค่า log₂ ของเลขกลมๆ ไว้ จะประมาณได้เร็ว

แม้ N ใหญ่ถึง 10¹⁸ ลูปที่หารสองทุกรอบก็วนแค่ราว 60 รอบ นี่คือเหตุผลที่ binary search ในบทที่ 19 เร็วมาก

recursion

หลักของ recursion คือ เวลา = จำนวนครั้งที่เรียก × งานในแต่ละครั้ง ไม่นับงานในครั้งที่ถูกเรียกต่อ เพราะครั้งเหล่านั้นนับเป็นครั้งของตัวเองแล้ว วิธีที่ง่ายที่สุดคือวาดต้นไม้ของการเรียกแบบหน้า 9.3 แล้วนับว่ามีกี่กล่อง

#include <bits/stdc++.h>
using namespace std;

long long total_calls = 0, half_calls = 0, split_work = 0;

long long total(int n)
{
    total_calls++;
    if (n == 0) {
        return 0;
    }
    return n + total(n - 1);
}

int halvings(int n)
{
    half_calls++;
    if (n <= 1) {
        return 0;
    }
    return 1 + halvings(n / 2);
}

void split(int n)
{
    split_work += n;
    if (n == 1) {
        return;
    }
    split(n / 2);
    split(n - n / 2);
}

int main()
{
    int n;
    cin >> n;
    long long sum = total(n);
    cout << "total = " << sum << ", calls = " << total_calls << '\n';
    int times = halvings(n);
    cout << "halvings = " << times << ", calls = " << half_calls << '\n';
    split(n);
    cout << "split work = " << split_work << '\n';
    return 0;
}

1024

total = 524800, calls = 1025
halvings = 10, calls = 11
split work = 11264

• total(n) เรียก total(n - 1) ต่อหนึ่งครั้ง ไล่ลงไปจนถึง 0 จึงเรียก N + 1 ครั้ง ครั้งละ O(1) รวมเป็น O(N) เหมือนลูปชั้นเดียว
• halvings(n) เรียกต่อด้วย n / 2 ขนาดลดลงครึ่งหนึ่งทุกครั้ง จึงเรียกแค่ log₂ N + 1 ครั้ง เป็น O(log N) เหมือนลูปหารสอง
• split(n) ทำงาน n หน่วย แล้วแบ่งเป็นสองครึ่งไปทำต่อ แต่ละครั้งทำงานไม่เท่ากัน ต้องดูทั้งต้นไม้

ต้นไม้ของ split(8) มีกล่องเยอะขึ้นเท่าตัวทุกชั้น แต่แต่ละกล่องเล็กลงครึ่งหนึ่ง งานรวมของแต่ละชั้นจึงเท่ากับ N เสมอ ส่วนจำนวนชั้นเท่ากับจำนวนครั้งที่หาร N ด้วยสองจนเหลือ 1 บวกหนึ่ง คือ log₂ N + 1 งานทั้งหมดจึงเป็น N × (log₂ N + 1) ซึ่ง N = 1024 ได้ 1024 × 11 = 11264 ตรงกับที่โปรแกรมนับ เป็น O(N log N) รูปร่างนี้คือ merge sort ที่จะเรียนในบทที่ 22

เทียบกับ fib(n) ในหน้า 9.3 ที่เรียกต่อสองครั้งเหมือนกัน แต่ขนาดลดลงแค่ 1 และ 2 ไม่ใช่ลดครึ่ง ต้นไม้จึงลึกเกือบ N ชั้นและกล่องเกือบเพิ่มเท่าตัวทุกชั้น fib(40) เรียกตัวเองถึง 331,160,281 ครั้งตามตารางในหน้านั้น เป็นงานแบบ exponential ใช้ O(2^N) เป็นขอบบนได้ สรุปเป็นหลักจำง่ายๆ

ลองทำให้พัง

ลูปคูณสองที่ไม่จบ

ลูป doubling ข้างบนดูปลอดภัย วนแค่ราว 30 รอบแม้ N เป็นพันล้าน ลองแยกออกมาเป็นโปรแกรมเดี่ยว แล้วป้อนค่ามากสุดของ int

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int steps = 0;
    for (int i = 1; i <= n; i *= 2) {
        steps++;
    }
    cout << "steps = " << steps << '\n';
    return 0;
}

2147483647

บนเครื่องที่เขียนเอกสารนี้ โปรแกรมไม่พิมพ์อะไรเลยและไม่จบเอง ทั้งแบบ Code::Blocks และแบบ -O2 ลองค่าอื่นพบว่า 1073741823 ยังได้ steps = 30 แต่ 1073741824 ค้างเหมือนกัน เลขนี้คือ 2³⁰ พอ i เป็น 2³⁰ ซึ่งยังไม่เกิน n ลูปจึงคูณสองต่อ ได้ 2³¹ ซึ่งเกิน int และล้นแบบในหน้า 1.3 การล้นของ int เป็น undefined behavior บนเครื่องนี้ผลที่ได้คือลูปไม่หยุดอีกเลย grader จะตัดจบแล้วให้ผล Time Limit Exceeded ทั้งที่เราคิดว่าวนแค่ 31 รอบ

แก้ด้วยการประกาศตัวแปรที่คูณเพิ่มเป็น long long ค่าจะไปถึง 2³¹ ได้โดยไม่ล้น แล้วลูปหยุดตามปกติ

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int steps = 0;
    for (long long i = 1; i <= n; i *= 2) {
        steps++;
    }
    cout << "steps = " << steps << '\n';
    return 0;
}

2147483647

steps = 31

กับดักเดียวกันเกิดกับ i * i <= n ในหน้า 4.5 เมื่อไรที่ตัวแปรในลูปโตแบบคูณ ให้ถามตัวเองว่าค่าสุดท้ายก่อนลูปหยุดใหญ่แค่ไหน ไม่ใช่แค่ค่าที่ยังอยู่ในขอบเขต

สรุป

• ทำต่อกันให้บวกแล้วเก็บตัวที่ใหญ่สุด ซ้อนกันให้คูณ if else ใช้ฝั่งที่แย่กว่า
• ลูปในที่วนจำนวนคงที่ เช่น 26 ตัวอักษร ไม่ทำให้ Big O เพิ่ม
• ตัวแปรคูณสองหรือหารสองทุกรอบ วนราว log₂ N รอบ 10⁹ ได้ราว 30
• ลูปในที่กระโดดทีละ i รวมได้ N/1 + N/2 + ... เป็น O(N log N)
• recursion ใช้เวลาเท่ากับจำนวนครั้งที่เรียกคูณงานต่อครั้ง แบ่งครึ่งสองทางแล้วทำงาน n ต่อครั้งได้ O(N log N) ลดทีละหนึ่งสองทางได้ exponential
• ตัวแปรที่คูณเพิ่มในลูปต้องใหญ่พอสำหรับค่าที่เกินขอบเขตไปหนึ่งรอบ