18.1 นับการทำงานและ Big O

ตั้งแต่บทนี้ไป โจทย์ยากขึ้นในแบบที่ต่างจากเดิม เขียนให้ได้คำตอบถูกยังไม่พอ ต้องได้คำตอบภายในเวลาที่โจทย์กำหนดด้วย และต้องเลือกวิธีที่ทันเวลาได้ตั้งแต่ก่อนพิมพ์โค้ดบรรทัดแรก ไม่ใช่เขียนเสร็จแล้วค่อยลุ้นตอนส่ง หน้านี้สอนเครื่องมือที่ใช้คิดเรื่องนี้ คือการนับว่าโปรแกรมต้องทำงานกี่ครั้ง และการเขียนผลที่นับได้ให้สั้นด้วยสัญลักษณ์ที่เรียกว่า Big O

ขอบเขตในโจทย์บอกวิธี

วิธีแรกที่คนส่วนใหญ่นึกออกคือเทียบทุกคู่ ลูปนอกหยิบคนที่ i ลูปในหยิบทุกคนที่อยู่หลังคนที่ i เจอคู่ไหนเท่ากันก็ตอบได้ทันที

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> code(n);
    for (int i = 0; i < n; i++) {
        cin >> code[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (code[i] == code[j]) {
                cout << "duplicate\n";
                return 0;
            }
        }
    }
    cout << "all different\n";
    return 0;
}

6
4012 3307 5121 2290 3307 4410

duplicate

โปรแกรมถูกและผ่านตัวอย่าง คำถามคือส่งแล้วจะทันเวลา 1 วินาทีไหม คำถามนี้ตอบได้โดยไม่ต้องส่ง และไม่ต้องรันด้วยซ้ำ แค่นับว่าโปรแกรมต้องทำงานกี่ครั้งเมื่อ N ใหญ่ที่สุดตามขอบเขต แล้วเทียบกับหลักจากหน้า 4.5 ที่ว่า 1 วินาทีทำงานง่ายๆ ได้ราว 10⁸ ครั้ง

นับจำนวนการทำงาน

ไม่ต้องนับทุกบรรทัด ให้หาบรรทัดที่ทำบ่อยที่สุด ซึ่งมักเป็นบรรทัดในลูปชั้นในสุด ในโปรแกรมนี้คือการเทียบ code[i] == code[j] ในบรรทัดที่ 16 แล้วนับว่าทำกี่ครั้งใน กรณีแย่ที่สุด (worst case) ซึ่งคือกรณีที่ไม่มีใครซ้ำเลย ลูปจึงไม่ได้หยุดกลางทาง

• i = 0 ลูปใน j วิ่งตั้งแต่ 1 ถึง N − 1 เทียบ N − 1 ครั้ง
• i = 1 เทียบ N − 2 ครั้ง
• ไปเรื่อยๆ จนถึง i = N − 1 ซึ่งเทียบ 0 ครั้ง

รวมเป็น (N − 1) + (N − 2) + ... + 1 + 0 ใช้สูตรผลรวมเลขเรียงที่เคยใช้ในแบบฝึกหัดบทที่ 1 ได้ N(N − 1) / 2 ครั้ง

ส่วนการอ่านข้อมูลในบรรทัดที่ 11 ถึง 13 ทำแค่ N ครั้ง น้อยกว่ากันมากจนไม่ต้องสนใจ คำตอบคือ วิธีนี้ไม่ทัน รู้ได้ตั้งแต่ยังไม่ได้ส่ง

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

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

bool seen[1000001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int code;
        cin >> code;
        if (seen[code]) {
            cout << "duplicate\n";
            return 0;
        }
        seen[code] = true;
    }
    cout << "all different\n";
    return 0;
}

5
4012 3307 5121 2290 4410

all different

แต่ละเลขที่อ่านเข้ามา ทำแค่เช็กช่องหนึ่งช่องกับทำเครื่องหมายหนึ่งครั้ง กรณีแย่ที่สุดทำ N รอบ N = 100,000 ก็แค่หนึ่งแสนรอบ ทันสบาย อาเรย์ seen อยู่นอก main ตามหน้า 5.5 จึงเริ่มเป็น false ทุกช่องโดยไม่ต้องวนลูปใส่ค่าเอง

Big O ตัดค่าคงที่และพจน์เล็ก

จำนวนครั้งที่นับได้ เขียนเป็นสูตรของ N ได้เสมอ วิธีเทียบทุกคู่คือ N(N − 1) / 2 ซึ่งกระจายได้เป็น ½N² − ½N ลองแทน N = 100,000 ดูทีละส่วน

ส่วน ½N เล็กกว่าส่วนแรกแสนเท่า ตัดทิ้งได้เลยโดยแทบไม่เปลี่ยนอะไร ส่วนตัวคูณ ½ ข้างหน้า จะเป็น 5 × 10⁹ หรือ 10¹⁰ ก็ไม่ทันเหมือนกัน สิ่งที่ตัดสินจริงๆ คือ รูปร่าง ของสูตร คือ N² ซึ่งบอกว่า N เพิ่ม 10 เท่า งานเพิ่ม 100 เท่า ตรงกับที่เห็นในตารางเวลาของ selection sort กับ insertion sort ในหน้า 13.3

เราจึงเขียนสั้นๆ ว่าวิธีนี้มีความซับซ้อนของเวลา (time complexity) เป็น O(N²) อ่านว่า โอของเอ็นกำลังสอง หรือ big O of N squared แปลว่าจำนวนการทำงานโตไม่เร็วกว่า N² คูณค่าคงที่สักตัว ส่วนวิธีอาเรย์นับเป็น O(N) วิธีหาคือ

1. นับจำนวนการทำงานในกรณีแย่ที่สุด เขียนเป็นสูตรของ N
2. เก็บไว้เฉพาะพจน์ที่โตเร็วที่สุด
3. ตัดตัวคูณที่เป็นค่าคงที่ทิ้ง

ความซับซ้อนที่เจอบ่อย

ก่อนดูตาราง ต้องรู้จัก log ก่อน log₂ N คือจำนวนครั้งที่หาร N ด้วยสองไปเรื่อยๆ จนเหลือ 1 เช่น 1024 หารสองได้ 10 ครั้ง log₂ 1024 จึงเป็น 10 ค่านี้โตช้ามาก 10⁶ หารสองได้ราว 20 ครั้ง และ 10⁹ ราว 30 ครั้ง ใน Big O ไม่ต้องเขียนฐาน เพราะ log ฐานสิบกับฐานสองต่างกันแค่ตัวคูณคงที่ราว 3.32 ซึ่งถูกตัดทิ้งอยู่แล้ว

แต่ละแบบโตเร็วแค่ไหน

แทนค่า N ลงในแต่ละสูตร จะเห็นว่าความต่างไม่ใช่สองสามเท่า แต่เป็นหลักล้านหลักพันล้านเท่า

กราฟข้างล่างวาดจากสูตรเดียวกันตามสเกลจริง แต่แกนทั้งสองเป็นแบบ สเกล log คือระยะห่างเท่ากันแทนการคูณเท่ากัน ไม่ใช่การบวกเท่ากัน แกนนอนเส้นตารางแต่ละเส้นห่างกัน 10 เท่า แกนตั้งห่างกัน 100 เท่า ต้องวาดแบบนี้เพราะถ้าใช้สเกลธรรมดา เส้น N กับ log N จะแบนติดพื้นจนมองไม่เห็น ขณะที่ 2^N พุ่งทะลุหน้าจอตั้งแต่ N ยังไม่ถึง 30 ส่วน O(1) คือเส้นนอนที่ติดพื้นของกราฟพอดี จึงไม่ได้วาดไว้

จุดบนเส้นประคือตำแหน่งที่แต่ละสูตรมีค่าถึง 10⁸ อ่านค่า N ใต้จุดนั้นได้ว่า วิธีแบบนี้รับ N ได้ใหญ่สุดเท่าไรในเวลาราว 1 วินาที

• N! ถึง 10⁸ ตั้งแต่ N ราว 11 และ 2^N ที่ N ราว 26 สองเส้นนี้เกือบตั้งฉาก เพิ่ม N นิดเดียวงานก็เพิ่มหลายเท่า
• N³ ถึงที่ N ประมาณ 460 และ N² ที่ N = 10⁴ พอดี
• N log N ถึงที่ N ประมาณ 4.5 ล้าน ส่วนเส้น N ต้องถึง N = 10⁸ ซึ่งเลยขอบขวาของกราฟไปแล้ว

ตัวเลขเหล่านี้คิดจากสูตรล้วนๆ หน้าถัดไปจะวัดเวลาจริงบนเครื่อง แล้วสรุปเป็นตารางว่าขอบเขต N แต่ละขนาดต้องใช้วิธีแบบไหน

ลองทำให้พัง

ทดสอบด้วยข้อมูลสุ่มอย่างเดียว

สมมติว่าน้องไม่ได้นับก่อน แต่ทดสอบโปรแกรม dup-pairs ด้วยการสร้างเลขสุ่มตั้งแต่ 1 ถึง 1000000 มา 100,000 ตัว แล้วรัน เสร็จเร็วมาก เลยคิดว่าผ่านแน่ จากนั้นลองอีกชุดที่เป็นเลข 1 ถึง 100,000 สลับลำดับกัน ไม่มีตัวไหนซ้ำเลย

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

dup-pairs โปรแกรมเดียวกัน ข้อมูลขนาดเท่ากัน แต่ช้ากว่ากันราว 48 เท่า เพราะเลขสุ่มหนึ่งแสนตัวจากหนึ่งล้านค่า แทบแน่นอนว่ามีคู่ที่ซ้ำโผล่มาตั้งแต่ช่วงต้น ลูปจึงหยุดเร็ว ส่วนชุดที่ไม่ซ้ำบังคับให้เทียบครบทั้ง 4,999,950,000 คู่ ชุดทดสอบที่ดีต้องมีกรณีแย่ที่สุดแบบนี้ จึงต้องคิดไว้ก่อนว่ามีอยู่เสมอ และถ้าขอบเขตเป็น N ≤ 200000 งานจะเพิ่มขึ้นอีก 4 เท่า

ส่วน dup-seen ซึ่งเป็นอีกโปรแกรมหนึ่งที่เป็น O(N) ใช้เวลาเกือบเท่า dup-pairs กับชุดสุ่ม แม้เจอกรณีแย่ที่สุด เวลาส่วนใหญ่ของมันคือการอ่านข้อมูล บทเรียนคือ อย่าตัดสินความเร็วจากข้อมูลที่บังเอิญง่าย ให้นับจากกรณีแย่ที่สุดก่อนเขียน ถ้าจะทดสอบเวลา ต้องสร้างข้อมูลที่บังคับให้โปรแกรมทำงานมากที่สุด

สรุป

• ก่อนเขียน ให้นับว่าบรรทัดที่ทำบ่อยที่สุดทำกี่ครั้งในกรณีแย่ที่สุด แล้วเทียบกับ 10⁸ ครั้งต่อวินาที
• Big O เก็บเฉพาะพจน์ที่โตเร็วที่สุดและตัดตัวคูณคงที่ เช่น N(N − 1) / 2 เป็น O(N²)
• log₂ N คือจำนวนครั้งที่หารสองจนเหลือ 1 10⁶ ได้ราว 20 และ 10⁹ ได้ราว 30
• เรียงจากเร็วไปช้า O(1) O(log N) O(N) O(N log N) O(N²) O(N³) O(2^N) O(N!)
• ทดสอบเวลาด้วยข้อมูลที่แย่ที่สุด ไม่ใช่ข้อมูลสุ่ม