Big O Notation là gì?

Bài viết được sự cho phép của tác giả Nguyễn Hữu Khanh

Chúng ta thường nghe nói về các thuật toán nhanh và hiệu quả khi thực hiện một tác vụ nào đó, nhưng nhanh và hiệu quả ở đây được hiểu như thế nào? Có phải nó được đo bằng thời gian thực hiện xong tác vụ đó trong vài giây hay vài phút hay không? Câu trả lời là không các bạn ạ!

Chương trình trên máy tính của mình chạy chậm hơn trên máy tính của các bạn bởi vì mình đang sử dụng một máy tính cũ hoặc bởi vì trong lúc chạy chương trình này mình còn chạy rất nhiều chương trình khác nữa,… Vì thế, khi chương trình trên máy tính của mình chạy chậm hơn trên máy tính của bạn không có nghĩa là bạn đang sử dụng một thuật toán hiệu quả hơn của mình. Do đó, khi so sánh hai thuật toán bất kỳ thực hiện cho một tác vụ nào đó, chúng ta không thể dựa vào thời gian thực thi tác vụ đó.

Để giải quyết vấn đề này, khái niệm Big O Notation đã được đưa ra để định nghĩa, đo lường tính hiệu quả của một thuật toán. Nó dựa vào số bước cần thực hiện của một thuật toán cho một tác vụ nào đó để đo lường tính hiệu quả của thuật toán đó. Cụ thể nó như thế nào, chúng ta hãy cùng xem xét các ví dụ sau nhé:

Ví dụ thứ nhất:

private int getLastElement(int[] numbers) {
return numbers[numbers.length - 1];
}

Các bước thực hiện trong phương thức trên là:

• Lấy thuộc tính length của mảng numbers (1)
• Thực hiện phép tính numbers.length – 1 (2)
• Sau khi có kết quả ở bước (2) thì lấy giá trị tại index này trong mảng numbers. (3)
• Và cuối cùng là return lại kết quả. (4)

Như vậy, phương thức trên, thuật toán của chúng ta sẽ trải qua tất cả 4 bước cho dù số lượng dữ liệu trong mảng numbers có lớn như thế nào!

Nếu quy về dạng hàm số mà các bạn đã được học ở phổ thông thì chúng ta có thể biểu diễn thuật toán trên như sau:

f(n) = 4

với n là số lượng dữ liệu trong mảng của chúng ta.

Nào, hãy xem xét ví dụ thứ hai nhé các bạn:

public static int sum(int[] numbers) {
int sum = 0;
for (int i = 0; i < numbers.length; i++) {
sum = sum + numbers[i];
}
return sum;
}

Với ví dụ này, chúng ta có thể xác định số bước cần thực hiện của thuật toán này như sau:

• Ở ngoài vòng lặp for, chúng ta có 3 bước bao gồm:
  • Khởi tạo biến sum với giá trị 0
  • Khởi tạo biến i với giá trị 0
  • Return lại giá trị của biến sum

• Trong vòng lặp for, với mỗi phần tử trong mảng numbers thì chúng ta lại có các bước như sau:
  • Lấy thuộc tính length của mảng numbers (1)
  • So sánh kết quả của bước (1) với biến i (2)
  • Lấy giá trị của mảng numbers tại index i (3)
  • Cộng biến sum với giá trị tại bước (4)
  • Gán giá trị ở bước (4) vào lại biến sum (5)
  • Tăng giá trị của biến i lên 1 (6)

Như vậy, trong vòng lặp for, với mỗi phần tử trong mảng numbers, chúng ta có 6 bước cần thực hiện. n là số phần tử trong mảng numbers thì chúng ta có 6n bước cần thực hiện.

Tổng cộng, chúng ta có 6n + 3 bước cần thực hiện cho thuật toán trong phương thức này. Dưới dạng hàm số, chúng ta có thể biểu diễn như sau:

f(n) = 6n + 3

Như vậy, như các bạn thấy, với ví dụ thứ nhất, rõ ràng số bước cần thực hiện không phụ thuộc vào số lượng dữ liệu mà chúng ta đưa vào. Còn ở ví dụ thứ hai, dữ liệu đưa vào của chúng ta càng lớn thì số bước cần thực hiện của chúng ta lại tăng theo.

Và ở đây, các bạn sẽ thấy, chúng ta sẽ có một hàm g(n) khác sao cho kể từ một giá trị n >= n0, giá trị của hàm g(n) nhân với một hằng số nào đó c0 luôn luôn lớn hơn giá trị của hàm f(n). Khi đó, hàm g(n) gọi là cận trên của hàm f(n) và hàm f(n) gọi là Big O của hàm g(n), viết là f(n) = O(g(n)).

Trong ví dụ thứ hai, chúng ta có thể gọi hàm g(n) = n là Big O của hàm f(n) = 6n + 3. Bởi vì ở đây, khi giá trị của n0 >= 3, c0 = 7 thì:
f(n) = 21
c0 * g(n) = 21
giá trị của hàm f(n) luôn nhỏ hơn hoặc bằng giá trị của hàm g(n) nhân với một hằng số c0.

Chúng ta có thể định nghĩa của Big O Notation như sau:

f(n) = O(g(n)) khi tồn tại một n0 > 0 và c0 > 0 sao cho:
f(n) <= c0 * g(n) với n >= n0.

Trong ví dụ thứ nhất, thì f(n) là một Big O của một hằng số, gọi là O(1).

Ở ví dụ thứ hai thì f(n) là một Big O của n, gọi là O(n).

Như vậy, Big O Notation là một khái niệm để xác định khả năng mở rộng của một thuật toán dựa vào số bước thực hiện của thuật toán đó. Chúng ta có thể dự đoán được thuật toán đó với dữ liệu ngày càng lớn thì sẽ như thế nào. Và cho phép chúng ta ước lượng được trường hợp xấu nhất dựa vào cận trên của thuật toán này.