DEV Community

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

Posted on • Originally published at pargorn.com

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

Big-O Notation

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

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

O(1) - Constant Time

  • เส้นกราฟจะเป็นเส้นตรงแนวนอน ซึ่งหมายความว่าเวลาในการทำงานไม่เปลี่ยนแปลงตามขนาดของข้อมูล > การเข้าถึงค่าในอาร์เรย์โดยใช้เลขดัชนี (Index)
void constantTimeExample(int arr[], int size) {
    int value = arr[0];  // O(1)
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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

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;
}
Enter fullscreen mode Exit fullscreen mode

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

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

เติบโตเร็วกว่า 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)
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

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

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)
}
Enter fullscreen mode Exit fullscreen mode

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

ความสัมพันธ์ของ 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

Speedy emails, satisfied customers

Postmark Image

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay