18.2 ขอบเขตโจทย์กับเวลาจริง

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

วัดเวลาแต่ละแบบ

ใช้วิธีเดียวกับหน้า 13.3 คือสร้างข้อมูลด้วย rand() หลัง srand(2569) แล้วใช้ clock() จับเฉพาะช่วงที่คำนวณ ไม่นับเวลาสร้างข้อมูล ตัวอย่างนี้คืองาน O(N²) นับคู่ i < j ที่ตัวหน้ามากกว่าตัวหลัง

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

int main()
{
    int n;
    cin >> n;
    srand(2569);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = rand();
    }
    clock_t start = clock();
    long long pairs = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] > a[j]) {
                pairs++;
            }
        }
    }
    clock_t end = clock();
    cout << "pairs = " << pairs << '\n';
    cout << "time = " << fixed << setprecision(3) << (double)(end - start) / CLOCKS_PER_SEC << " seconds\n";
    return 0;
}

10000

pairs = 25213976
time = 0.068 seconds

บรรทัดสุดท้ายใช้ fixed กับ setprecision(3) จากหน้า 15.2 พิมพ์เวลาเป็นทศนิยม 3 ตำแหน่ง ส่วนเลขของ pairs ขึ้นกับ rand() ของเครื่อง บนเครื่องอื่นอาจได้ไม่เท่านี้

งานแบบอื่นใช้โครงเดียวกัน เปลี่ยนแค่ส่วนที่จับเวลา ทุกตัววัดบนเครื่องเดียวกับหน้า 4.5 คือโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 Windows 11 เสียบสายชาร์จ โหมดพลังงาน Balanced คอมไพล์ด้วย GCC 14.2 ของ Code::Blocks แบบ -O2 อย่างเดียว เพราะ grader คอมไพล์แบบนี้ แต่ละช่องคือค่ากลางของ 5 ครั้ง

อ่านตารางได้สามเรื่อง

1. ทุกแถวโตตามรูปร่างของ Big O sort ข้อมูลเพิ่ม 10 เท่า เวลาเพิ่มราว 10 เท่า งาน O(N³) N เพิ่ม 2 เท่า เวลาเพิ่มราว 8 เท่า งาน O(2^N) N เพิ่มแค่ 5 เวลาเพิ่มราว 36 เท่า ใกล้กับ 2⁵ = 32
2. บางแถวโตเร็วกว่าที่นับได้ O(N²) จาก 10⁴ เป็น 10⁵ ควรเพิ่ม 100 เท่า แต่เพิ่มราว 200 เท่า และ O(N!) จาก 11 เป็น 12 ควรเพิ่มราว 12 เท่า แต่เพิ่มราว 23 เท่า ส่วนที่เกินมาจากรายละเอียดการทำงานของซีพียูแบบเดียวกับ bubble sort ในหน้า 13.3 จึงควรเผื่อเวลาไว้เสมอเมื่อข้อมูลใหญ่
3. งานง่ายๆ เร็วกว่า 10⁸ ครั้งต่อวินาที งาน O(N³) ที่ N = 2,000 เทียบสามตัวไปราว 1.3 × 10⁹ ครั้ง ใช้ไม่ถึงวินาที เพราะลูปในสุดเรียบง่ายมาก งานจริงในโจทย์มักทำมากกว่านี้ต่อรอบ และเครื่องของ grader อาจช้ากว่า หลัก 10⁸ จึงยังเป็นตัวเลขที่ปลอดภัย

ตารางขอบเขต

เอาหลัก 10⁸ ครั้งต่อวินาทีกับตารางเวลาข้างบนมารวมกัน ได้ตารางที่ใช้กันทั่วไปในวงการแข่งขัน สำหรับโจทย์ที่จำกัดเวลา 1 วินาที

วิธีใช้คือ อ่านขอบเขตก่อนอ่านเรื่องราวในโจทย์ด้วยซ้ำ ถ้าเห็น 1 ≤ N ≤ 100000 ให้รู้ทันทีว่าลูปซ้อนสองชั้นที่ไล่ทุกคู่ใช้ไม่ได้ ต้องหาวิธี O(N log N) หรือเร็วกว่า ถ้าเห็น N ≤ 20 ก็แปลว่าคนตั้งโจทย์ตั้งใจให้ลองทุกแบบได้ ขอบเขตที่เล็กผิดปกติคือคำใบ้

ถ้ามีหลายตัวแปร

โจทย์หลายข้อมีมากกว่าหนึ่งขอบเขต เช่น ข้อมูล N ตัว กับคำถาม Q ข้อ ต้องคูณกันตามโครงของลูป ในหน้า 5.4 ถ้าตอบแต่ละคำถามด้วยการบวกใหม่ทั้งช่วง งานคือ O(NQ) ถ้า N และ Q เป็นแสนทั้งคู่ก็คือ 10¹⁰ ไม่ทัน ผลรวมสะสมเตรียม O(N) ครั้งเดียวแล้วตอบคำถามละ O(1) รวมเป็น O(N + Q) ทันสบาย เห็นคำถามหลายข้อเมื่อไร ให้ถามตัวเองว่าตอบหนึ่งข้อใช้เวลาเท่าไร

ขอบเขตของค่าก็บอกวิธี

นอกจากจำนวนข้อมูล ให้ดูขอบเขตของค่าแต่ละตัวด้วย ค่าไม่เกิน 10⁶ ใช้อาเรย์นับได้ เพราะอาเรย์หนึ่งล้านช่องเล็กพอ แต่ถ้าค่าไปถึง 10⁹ อาเรย์นับใช้ไม่ได้ ต้องเปลี่ยนเป็น sort แล้วเทียบตัวที่ติดกัน หรือใช้ map ในบทที่ 20 การคำนวณว่าอาเรย์ใหญ่เกินหรือยังอยู่ในหน้า 18.4

ลองทำให้พัง

ลืมนับจำนวนชุดทดสอบ

โจทย์บางข้อให้หลายชุดทดสอบในไฟล์เดียว เช่น

เห็น N ≤ 10000 แล้วเปิดตาราง ไล่ทุกคู่ O(N²) ทันสบาย ก็เขียนตามนั้น

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        long long pairs = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (a[i] > a[j]) {
                    pairs++;
                }
            }
        }
        cout << pairs << '\n';
    }
    return 0;
}

2
4
3 1 4 2
3
5 5 1

3
2

วัดทั้งโปรแกรมด้วยเลขสุ่ม 1 ถึง 1000000 อ่านจากไฟล์ เครื่องเดิม -O2 ค่ากลางของ 5 ครั้ง

ชุดเดียวทันสบายจริง แต่ไฟล์ที่มี 100 ชุดเต็มขอบเขตใช้เวลาราว 67 เท่า งานจริงคือ T × N² / 2 = 5 × 10⁹ ไม่ใช่ N² / 2 จำนวนชุด T ก็เป็นตัวแปรที่ต้องคูณเข้าไป เหมือนจำนวนคำถาม Q ในหัวข้อก่อนหน้า โจทย์หลายข้อจึงเขียนกำกับไว้ว่า ผลรวมของ N ทุกชุดไม่เกินเท่าไร ถ้ามีประโยคนี้ ให้คิดจากผลรวมนั้น เช่น ผลรวมของ N ไม่เกิน 10000 แปลว่าทั้งไฟล์ไล่คู่รวมกันไม่เกินราว 5 × 10⁷ ครั้ง ถ้าไม่มี ให้คิดว่าทุกชุดใหญ่เต็มขอบเขต

อีกเรื่องที่ตารางเวลาในหน้านี้ไม่ได้นับ คือเวลาอ่านและพิมพ์ข้อมูล แต่ grader จับเวลาทั้งโปรแกรม ข้อมูลเป็นแสนเป็นล้านตัวต้องเปิด ios::sync_with_stdio(false); cin.tie(nullptr); และใช้ '\n' แทน endl ตามหน้า 15.3 ทุกครั้ง ไม่อย่างนั้นอัลกอริทึมที่ดีก็ไม่ช่วย

สรุป

• บนเครื่องที่เขียนเอกสารนี้แบบ -O2 sort 10⁶ ตัวใช้ 0.064 วินาที ไล่ทุกคู่ที่ N = 10⁵ ใช้ 13.6 วินาที
• ตารางขอบเขต N ≤ 11 ใช้ N! ได้ ≤ 25 ใช้ 2^N ได้ ≤ 500 ใช้ N³ ได้ ≤ 5,000 ใช้ N² ได้ ถึง 10⁶ ต้อง N log N ถึง 10⁷ ต้อง N
• มีหลายขอบเขต ให้คูณตามโครงลูป เช่น Q คำถาม คำถามละ N รอบ คือ O(NQ)
• ค่าไม่เกิน 10⁶ ใช้อาเรย์นับได้ ค่าถึง 10⁹ ใช้ไม่ได้
• มีหลายชุดทดสอบ ให้คูณจำนวนชุดเข้าไปด้วย เว้นแต่โจทย์บอกผลรวมของ N ทุกชุดไว้