22.1 แบ่ง แก้ย่อย รวม

น้องเจอการแบ่งครึ่งมาแล้วหลายที่ ยกกำลังแบบแบ่งครึ่งในหน้า 9.2 หอคอยฮานอยในหน้า 9.5 binary search ในหน้า 9.4 และบทที่ 19 และหน้า 13.4 ที่บอกว่า qsort เร็วเพราะแบ่งข้อมูลเป็นส่วนๆ แล้วจัดทีละส่วน ทั้งหมดนี้คือวิธีคิดเดียวกัน ชื่อว่า divide and conquer (แบ่งแล้วเอาชนะ) หน้านี้แยกวิธีคิดนั้นออกเป็นสามขั้น ดูว่าทำไมการแบ่งครึ่งทำให้ recursion ไม่ลึก และอ่านเวลาที่ใช้ได้จากรูปของการแบ่ง ก่อนจะเอาไปเรียงข้อมูลในหน้าถัดไป

สามขั้น

1. แบ่ง (divide) ตัดปัญหาเป็นปัญหาย่อยแบบเดียวกันที่เล็กกว่า ส่วนใหญ่ตัดเป็นสองครึ่ง
2. แก้ย่อย (conquer) เรียกตัวเองกับปัญหาย่อยแต่ละส่วน จนส่วนเล็กพอที่ตอบได้ทันที ซึ่งก็คือกรณีฐานในบทที่ 9
3. รวม (combine) เอาคำตอบของปัญหาย่อยมาประกอบเป็นคำตอบของปัญหาใหญ่

เริ่มจากตัวอย่างที่ง่ายที่สุด ร้านขนมจดยอดขายรายวันไว้ 8 วัน อยากได้ยอดรวม แบ่งวันเป็นครึ่งแรกกับครึ่งหลัง หายอดของแต่ละครึ่ง แล้วบวกกัน ส่วนที่เหลือวันเดียวคือกรณีฐาน ยอดของวันนั้นคือคำตอบเลย

ช่วงของวันเขียนแบบ [lo, hi) คือตั้งแต่ lo ถึง hi - 1 ไม่รวม hi แบบเดียวกับ lo กับ hi ในหน้า 19.1 ข้อดีคือช่วงยาว hi - lo พอดี และแบ่งที่ mid ได้สองช่วง [lo, mid) กับ [mid, hi) ที่ต่อกันสนิท ไม่ซ้ำและไม่ขาด ทั้งบทนี้ใช้แบบนี้

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

long long total(const vector<int> &sales, int lo, int hi, int depth)
{
    string indent(4 * depth, ' '); // (1)!
    if (hi - lo == 1) { // (2)!
        cout << indent << "day " << lo << " = " << sales[lo] << '\n';
        return sales[lo];
    }
    int mid = (lo + hi) / 2;
    cout << indent << "split [" << lo << ", " << hi << ") at " << mid << '\n';
    long long left = total(sales, lo, mid, depth + 1);
    long long right = total(sales, mid, hi, depth + 1);
    cout << indent << "[" << lo << ", " << hi << ") = " << left << " + " << right << " = " << left + right << '\n';
    return left + right; // (3)!
}

int main()
{
    int n;
    cin >> n;
    vector<int> sales(n);
    for (int i = 0; i < n; i++) {
        cin >> sales[i];
    }
    long long sum = total(sales, 0, n, 0);
    cout << "total = " << sum << '\n';
    return 0;
}

1. สร้าง string ที่มีช่องว่าง 4 * depth ตัว ใช้เยื้องตามความลึกแบบหน้า 9.1 จะได้เห็นว่าแต่ละบรรทัดอยู่ชั้นไหน
2. กรณีฐาน ช่วงเหลือวันเดียว ช่วง [lo, hi) ไม่มีทางว่าง เพราะเริ่มจาก n ที่ไม่น้อยกว่า 1 และแบ่งทีไรก็ได้สองช่วงที่ยาวอย่างน้อย 1
3. ขั้นรวมของปัญหานี้คือบวกเลขสองตัว ใช้เวลาคงที่

8
120 80 150 90 60 200 110 95

split [0, 8) at 4
    split [0, 4) at 2
        split [0, 2) at 1
            day 0 = 120
            day 1 = 80
        [0, 2) = 120 + 80 = 200
        split [2, 4) at 3
            day 2 = 150
            day 3 = 90
        [2, 4) = 150 + 90 = 240
    [0, 4) = 200 + 240 = 440
    split [4, 8) at 6
        split [4, 6) at 5
            day 4 = 60
            day 5 = 200
        [4, 6) = 60 + 200 = 260
        split [6, 8) at 7
            day 6 = 110
            day 7 = 95
        [6, 8) = 110 + 95 = 205
    [4, 8) = 260 + 205 = 465
[0, 8) = 440 + 465 = 905
total = 905

อ่านจากบนลงล่าง บรรทัด split คือขาลงที่แบ่ง บรรทัด day คือกรณีฐาน และบรรทัดที่มีเครื่องหมายบวกคือขากลับที่รวม ครึ่งซ้ายทำจนเสร็จก่อนแล้วจึงเริ่มครึ่งขวา เพราะ left ต้องได้ค่ามาก่อนจะไปบรรทัดที่เรียก right วาดเป็นต้นไม้ได้แบบนี้

ขาลงอ่านจากบนลงล่าง ทุกกล่องแตกเป็นสองกล่องที่เล็กลงครึ่งหนึ่ง จนถึงชั้นล่างสุดที่เหลือวันเดียว ขากลับอ่านจากล่างขึ้นบน แต่ละกล่องได้ค่าจากการบวกสองกล่องข้างล่าง ต้นไม้แบบนี้จะใช้ตลอดบท ทั้งดูว่าโปรแกรมทำอะไร และนับว่าใช้เวลาเท่าไร

ลึกแค่ log N ชั้น

หน้า 9.4 หาผลรวมของอาเรย์ด้วย recursion ที่ตัดทีละหนึ่งช่อง ลึกหนึ่งชั้นต่อหนึ่งช่อง แบบ Code::Blocks ป้อนคะแนน 33000 ตัวก็ stack เต็มแล้ว แบบแบ่งครึ่งต่างออกไป ทุกชั้นช่วงสั้นลงครึ่งหนึ่ง ต้นไม้จึงสูงแค่จำนวนครั้งที่หาร N ด้วยสองจนเหลือ 1 โปรแกรมนี้นับจำนวนครั้งที่เรียกและชั้นที่ลึกที่สุด ข้อมูลล้านวันสร้างจากสูตรเพื่อไม่ต้องพิมพ์เข้าไป

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

long long calls = 0;
int deepest = 0;

long long total(const vector<int> &sales, int lo, int hi, int depth)
{
    calls++;
    deepest = max(deepest, depth);
    if (hi - lo == 1) {
        return sales[lo];
    }
    int mid = (lo + hi) / 2;
    return total(sales, lo, mid, depth + 1) + total(sales, mid, hi, depth + 1);
}

int main()
{
    int n;
    cin >> n;
    vector<int> sales(n);
    for (int i = 0; i < n; i++) {
        sales[i] = i * 37 % 100 + 1;
    }
    long long by_loop = 0;
    for (int i = 0; i < n; i++) {
        by_loop += sales[i];
    }
    long long by_split = total(sales, 0, n, 0);
    cout << "loop  = " << by_loop << '\n';
    cout << "split = " << by_split << '\n';
    cout << "calls = " << calls << ", deepest = " << deepest << '\n';
    return 0;
}

1000000

loop  = 50500000
split = 50500000
calls = 1999999, deepest = 20

ล้านช่องลึกแค่ 20 ชั้น เพราะ 2²⁰ ราวหนึ่งล้าน stack ไม่มีทางเต็ม จำนวนครั้งที่เรียกคือ 2N - 1 พอดี มีกรณีฐาน N ครั้ง ครั้งละหนึ่งวัน และกล่องที่แบ่ง N - 1 ครั้ง เพราะทุกครั้งที่แบ่ง จำนวนชิ้นเพิ่มขึ้นหนึ่ง จากหนึ่งชิ้นไปเป็น N ชิ้น

แบ่งแล้วเร็วขึ้นไหม

ผลรวมแบบแบ่งครึ่งเรียกฟังก์ชันสองล้านครั้งเพื่อบวกเลขล้านตัว ส่วนลูปบวกล้านครั้งเฉยๆ ทั้งคู่เป็น O(N) แต่การเรียกฟังก์ชันมีค่าใช้จ่าย วัดด้วย clock() แบบหน้า 13.3 กับข้อมูล 10⁷ วัน บนเครื่องเดียวกับหน้า 13.3 คือโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 Windows 11 เสียบสายชาร์จ คอมไพล์ด้วย g++ 14.2 ของ Code::Blocks รันแต่ละแบบ 5 ครั้ง ตารางเป็นค่ากลาง ทั้งบทนี้วัดแบบเดียวกันนี้

แบ่งครึ่งช้ากว่าลูปราวสามถึงสี่เท่า การแบ่งเฉยๆ ไม่ได้ทำให้เร็วขึ้น ถ้าทุกส่วนยังต้องทำครบ และขั้นรวมก็ไม่ได้ประหยัดอะไร ทางที่ divide and conquer เร็วกว่าวิธีตรงไปตรงมาซึ่งเจอบ่อยในค่ายมีสองทาง

• ทิ้งได้ทั้งส่วน รู้ว่าคำตอบอยู่ส่วนไหน ก็ไม่ต้องทำอีกส่วนเลย แบบ binary search
• ขั้นรวมถูกกว่าทำทั้งก้อน เช่น เรียงสองครึ่งแยกกัน แล้วรวมสองครึ่งที่เรียงแล้วในเวลา O(N) ถูกกว่าเรียงทั้งก้อนด้วย insertion sort ที่เป็น O(N²) ซึ่งคือ merge sort ในหน้าถัดไป

decrease and conquer เมื่อเหลือส่วนเดียว

ถ้าแบ่งแล้วต้องแก้แค่ส่วนเดียว เรียกว่า decrease and conquer (ลดขนาดแล้วเอาชนะ) เป็นกรณีพิเศษที่เร็วที่สุดของ divide and conquer น้องเขียนมาแล้วสองตัว

• binary search ในหน้า 19.1 ดูช่อง mid แล้วทิ้งครึ่งที่คำตอบไม่มีทางอยู่ เหลือส่วนเดียวที่เล็กลงครึ่งหนึ่ง ขั้นรวมไม่มีเลย คำตอบของส่วนที่เหลือคือคำตอบทั้งหมด
• ยกกำลังแบบแบ่งครึ่ง ในหน้า 9.2 และ 12.1 คำนวณ a^n/2 ครั้งเดียว เก็บไว้ในตัวแปร แล้วยกกำลังสอง ขั้นรวมคือคูณหนึ่งหรือสองครั้ง

ส่วนที่เหลือเล็กลงครึ่งหนึ่งทุกครั้ง และขั้นรวมใช้เวลาคงที่ ทั้งสองจึงเป็น O(log N) ส่วนการเขียนผิดในหน้า 9.2 ที่เรียก fast_power(base, exponent / 2) สองครั้ง กลายเป็นปัญหาย่อยสองส่วนเหมือนผลรวมข้างบน จึงตกไปเป็น O(N) และนับได้ 2097151 ครั้งที่เลขชี้กำลังหนึ่งล้าน หน้า 22.4 จะเห็น decrease and conquer อีกตัวคือ quickselect

อ่านเวลาจากรูปของการแบ่ง

หน้า 18.3 นับเวลาของ recursion จากต้นไม้ของการเรียก แต่ละชั้นของต้นไม้มีงานรวมเท่าไร คูณด้วยจำนวนชั้น ใช้กับทุกวิธีในบทนี้ได้ตามตาราง

แถวที่สองกับแถวที่สามได้ O(N) ด้วยเหตุผลต่างกัน แถวที่สองงานแต่ละชั้นลดลงครึ่งหนึ่ง N + N/2 + N/4 + ... ไม่เกิน 2N แถวที่สามงานแต่ละครั้งคงที่ แต่จำนวนกล่องรวมคือ 2N - 1 ตามที่นับได้ข้างบน ส่วนแถวสุดท้ายแบ่งเป็นสองส่วนเหมือนกัน แต่ส่วนเล็กลงแค่หนึ่ง ไม่ใช่ครึ่งหนึ่ง ต้นไม้จึงลึก N ชั้น และกล่องเพิ่มเท่าตัวทุกชั้น ต้องแบ่งให้เล็กลงเป็นสัดส่วน ไม่ใช่ลดทีละหนึ่ง การแบ่งจึงจะคุ้ม

ลองทำให้พัง

แบบที่ 1 ใช้ช่วงปิดแต่แบ่งแบบช่วงเปิด

หลายคนคุ้นกับช่วงปิด [lo, hi] แบบ binary search ในหน้า 9.4 จึงเขียนกรณีฐานเป็น lo == hi แต่ตอนแบ่งยังส่ง mid ให้ทั้งสองฝั่งแบบช่วงเปิด

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

long long total(const vector<int> &sales, int lo, int hi)
{
    if (lo == hi) {
        return sales[lo];
    }
    int mid = (lo + hi) / 2;
    return total(sales, lo, mid) + total(sales, mid, hi);
}

int main()
{
    int n;
    cin >> n;
    vector<int> sales(n);
    for (int i = 0; i < n; i++) {
        cin >> sales[i];
    }
    long long sum = total(sales, 0, n - 1);
    cout << "total = " << sum << '\n';
    return 0;
}

ป้อนยอดขาย 8 วันชุดเดิม แบบ Code::Blocks ไม่พิมพ์อะไรเลยแล้วจบด้วย

Process returned -1073741571 (0xC00000FD)

รหัส 0xC00000FD คือ stack overflow ตามหน้า 9.1 ไล่ด้วยมือกับช่วง [0, 1] ที่มีสองวัน ได้ mid = 0 ฝั่งซ้ายเรียก total(0, 0) ซึ่งจบได้ แต่ฝั่งขวาเรียก total(0, 1) ซึ่งคือช่วงเดิมเป๊ะ ช่วงไม่เล็กลง จึงเรียกซ้ำไม่รู้จบ ส่วนแบบ -O2 compiler แปลงการเรียกฝั่งขวาเป็นลูป โปรแกรมจึงไม่พังแต่วนค้าง บนเครื่องที่เขียนเอกสารนี้รอ 10 วินาทีแล้วยังไม่จบ ส่งให้ grader จะได้ผลว่าเกินเวลา

เลือกแบบใดแบบหนึ่งแล้วใช้ให้ตลอด ช่วงปิดต้องแบ่งเป็น [lo, mid] กับ [mid + 1, hi] ช่วงเปิดแบ่งเป็น [lo, mid) กับ [mid, hi) แล้วทดสอบด้วยช่วงที่ยาวสองเสมอ เพราะเป็นช่วงที่สั้นที่สุดที่ยังต้องแบ่ง

แบบที่ 2 แบ่งไม่ครึ่ง

ในโปรแกรม deep-sum เปลี่ยนจุดแบ่งเป็น

int mid = lo + 1;

ผลรวมยังถูก เพราะ [lo, lo + 1) กับ [lo + 1, hi) ยังต่อกันสนิท จำนวนครั้งที่เรียกก็ยังเป็น 2N - 1 แต่ป้อน 1000 ได้ deepest = 999 แทนที่จะเป็น 10 เพราะทุกครั้งตัดออกแค่หนึ่งวัน กลายเป็น recursion ทีละช่องแบบหน้า 9.4 ป้อน 30000 แบบ Code::Blocks ก็พังด้วย 0xC00000FD แล้ว แบบ -O2 ผ่านถึงล้านเพราะ compiler แปลงฝั่งที่ลึกเป็นลูปให้ แต่ห้ามพึ่งเรื่องนี้ตามที่หน้า 9.1 เตือนไว้ การแบ่งไม่ครึ่งแบบนี้คือสิ่งที่เกิดกับ quicksort ในหน้า 22.4 เมื่อเลือกตัวแบ่งไม่ดี

สรุป

• divide and conquer มีสามขั้น แบ่งเป็นปัญหาย่อยแบบเดียวกัน แก้ย่อยด้วยการเรียกตัวเอง และรวมคำตอบ
• ใช้ช่วงแบบ [lo, hi) แบ่งที่ mid เป็น [lo, mid) กับ [mid, hi) กรณีฐานคือช่วงยาวหนึ่ง และทดสอบด้วยช่วงยาวสอง
• แบ่งครึ่งทำให้ลึกแค่ราว log₂ N ชั้น ล้านช่องลึก 20 ชั้น แต่ถ้าแบ่งไม่ครึ่งจะลึกถึง N ชั้น
• แบ่งเฉยๆ ไม่เร็วขึ้น ต้องทิ้งได้ทั้งส่วนแบบ decrease and conquer หรือขั้นรวมต้องถูกกว่าทำทั้งก้อน
• binary search กับยกกำลังแบบแบ่งครึ่งคือ decrease and conquer เหลือปัญหาย่อยส่วนเดียว จึงเป็น O(log N)
• อ่านเวลาจากต้นไม้ของการเรียก งานต่อชั้นคูณจำนวนชั้น สองส่วนครึ่งกับขั้นรวม O(n) ได้ O(N log N)