ทำความเข้าใจเกี่ยวกับ Big-O และตัวอย่างโค้ดในภาษา C++

Big-O Notation

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

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

O(1) - Constant Time

• เส้นกราฟจะเป็นเส้นตรงแนวนอน ซึ่งหมายความว่าเวลาในการทำงานไม่เปลี่ยนแปลงตามขนาดของข้อมูล > การเข้าถึงค่าในอาร์เรย์โดยใช้เลขดัชนี (Index)

void constantTimeExample(int arr[], int size) {
    int value = arr[0];  // O(1)
}

O(log n) - Logarithmic Time

• เส้นกราฟจะเป็นเส้นโค้งที่ค่อย ๆ เพิ่มขึ้น โดยมีอัตราการเพิ่มที่ลดลงเรื่อย ๆ
• Binary Search

int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;  // O(log n)
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

เติบโตช้าเมื่อขนาดข้อมูลเพิ่มขึ้น

O(n) - Linear Time

• เส้นกราฟจะเป็นเส้นตรงที่เพิ่มขึ้นตามขนาดของข้อมูล
• Linear Search

int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; ++i) {
        if (arr[i] == target) return i;  // O(n)
    }
    return -1;
}

เติบโตเป็นเส้นตรงตามขนาดข้อมูล

O(n log n) - Linearithmic Time

• เส้นกราฟจะเพิ่มขึ้นตามขนาดข้อมูลแบบไม่เป็นเส้นตรง และเร็วกว่าการเติบโตแบบเชิงเส้น
• Merge Sort และ Quick Sort

void merge(int arr[], int left, int mid, int right) {
    // Merge two halves
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);     // O(n log n)
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

เติบโตเร็วกว่า O(n) แต่ช้ากว่า O(n^2)

O(n^2) - Quadratic Time

• เส้นกราฟจะเป็นเส้นโค้งที่เติบโตเร็วขึ้นตามขนาดข้อมูล
• Bubble Sort

void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; ++i) {
        for (int j = 0; j < size - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);  // O(n^2)
            }
        }
    }
}

เติบโตเร็วขึ้นเรื่อย ๆ ตามขนาดข้อมูล

O(2^n) - Exponential Time

• เส้นกราฟจะเป็นเส้นโค้งที่เติบโตอย่างรวดเร็วมาก ตามขนาดข้อมูลที่เพิ่มขึ้น
• Fibonacci Recursive

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);  // O(2^n)
}

เติบโตเร็วมากจนอาจไม่สามารถใช้งานได้เมื่อขนาดข้อมูลใหญ่

ความสัมพันธ์ของ Big-O

ลองจินตนาการถึงกราฟที่แสดงค่า Big-O ต่าง ๆ โดยแกน x แทนขนาดของข้อมูล (n) และแกน y แทนเวลาในการประมวลผล

• O(1) เส้นตรงแนวนอนที่ค่าคงที่
• O(log n) เส้นโค้งที่ค่อย ๆ เพิ่มขึ้นในอัตราลดลง (เช่น เส้นโค้งลอการิทึม)
• O(n) เส้นตรงที่เพิ่มขึ้นอย่างสมมาตร
• O(n log n) เส้นโค้งที่เพิ่มขึ้นอย่างรวดเร็วขึ้นจาก O(n) แต่ช้ากว่า O(n^2)
• O(n^2) เส้นโค้งพาราโบลาที่เพิ่มขึ้นอย่างรวดเร็ว
• O(2^n) เส้นโค้งที่เติบโตอย่างรวดเร็วมาก คล้ายเส้นเอ็กซ์โพเนนเชียล

สรุป

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