Big O độ phức tạp thuật toán

Bài viết được sự cho phép của tác giả Võ Xuân Phong

O(n) là gì?

Giả sử mình có 1 hàm printElements như hình bên dưới, hàm này phải lặp n lần để in ra các giá trị i, vậy độ phức tạp của thuật toán Big O của hàm này sẽ là O(n)

Ngoài ra trong Big O còn có khái niệm Drop Constant, nó sẽ loại bỏ hằng số khi tính Big O. Ví dụ bên dưới, mình có 2 vòng lặp tách biệt nhau và mỗi vòng lặp chạy n lần, như vậy mình sẽ có phép cộng: Big O = O(n+n) = O(2n)

Ở đây mình có O(2n) và như mình đã nói ở trên mình có quyền loại bỏ hằng số, vậy cuối cùng Big O = O(n)

O(n^2) là gì?

Đi vào ví dụ mới, bên dưới mình có 2 vòng lặp lồng nhau, vòng lặp thứ nhất chạy qua n lần, mỗi lần vòng lặp thứ nhất chạy thì vòng lặp thứ hai phải chạy thêm n lần nữa, như vậy mình sẽ có phép nhân. Big O = O(n*n) = O(n^2)

O(n!) là gì?

n! đọc là n giai thừa là tích các số từ 1 đến chính nó, ví dụ:

0! = 1

1! = 1

2! = 1 * 2 = 2

3! = 1 * 2 * 3 = 6

4! = 1 * 2 * 3 * 4 = 24

5! = 1 * 2 * 3 * 4 * 5 = 120

6! = 1 * 2 * 3 * 4 * 5 * 6 = 720

Mình có đoạn code sau:

khi n thay đổi thì số lần lặp của hàm run sẽ tăng theo số n giai thừa, cho nên thuật toán trên có độ phức tạp là O(n!), dựa vào biểu đồ của các độ phức tạp thì độ phức tạp của thuật toán có O(n!) là rất tồi tệ. Một ví dụ khác cho thuật toán có độ phức tạp O(n!) là: https://en.wikipedia.org/wiki/Travelling_salesman_problem

O(log n) là gì?

Độ phức tạp O(log n) được gọi là độ phức tạp logarit. Ở đây mình có một ví dụ đơn giản:

Logarit cơ số 2 của 8 thì bằng bao nhiêu?

Log₂8 = ?

tương đương với 2 mũ bao nhiêu để bằng 8

2^? = 8

Ta có 2 mũ 3 sẽ bằng 8

2³=8

Như vậy số cần tìm ở đây sẽ là 3.

Ở ví dụ bên dưới mình có thuật toán Binary Search với input array đầu vào đã được sắp xếp theo thứ tự tăng dần, ở mỗi lần lặp thì thuật toán sẽ giảm đi một nửa số lượng phần tử, chia nhỏ mảng làm 2 phần, loại bỏ 1 phần và tính toán tiếp trên phần còn lại của mảng. Trong trường hợp tốt nhất thì giá trị cần tìm sẽ nằm ở giữa mảng, nhưng trong trường hợp xấu nhất thì nó sẽ nằm ở đầu hoặc cuối mảng. Giả sử mình đi tìm số 1 trong mảng, nó là con số ở đầu mảng tương ứng với trường hợp xấu nhất. Như đã thấy mình sẽ mất 3 lần lặp để có thể có thể tìm được giá trị trong mảng có 8 phần tử.

O(1) là gì?

O(1) là độ phức tạp hằng số, nó là độ phức tạp tốt nhất, chỉ cần thực hiện một thao tác mình đã có ngay kết quả. Ở ví dụ bên dưới mình có một hàm sum, hàm sum này sẽ nhận 2 input là n và m, tuy n và m có thể thay đổi nhưng cũng chỉ mất một thao tác tính toán thì mình có thể có kết quả ngày, hoặc việc truy cập vào một dictionary, truy cập ngay lập tức bằng key mà không cần phải lặp qua mảng thì đây là độ phức tạp O(1), độ phức tạp được xem là hoàn hảo nhất.

Tóm lại

– Để viết thuật toán hiệu quả thì nên hạn chế sử dụng các vòng lặp lồng nhau, nó sẽ làm tăng độ phức tạp của thuật toán và thời gian thực thi sẽ lâu hơn.

– Chọn cấu trúc dữ liệu phù hợp, ở mỗi bài toán khác nhau mình nên xem xét những cấu trúc dữ liệu nào hiệu quả nhất để áp dụng ví dụ như Dictionary, Hash Table, Linked List, Graph v.v.

– Thực hiện ghi nhớ các giá trị nếu cần thiết, tránh việc tính toán lặp lại.

– Áp dụng phương pháp chia để trị như ví dụ của thuật toán Binary Search với độ phức tạp là O(log n).

Bài viết gốc được đăng tải tại anhlamweb.com

Xem thêm: