BIg O

Tài nguyên cơ bản cần thiết cho một thuật toán là không gian làm việc của nó (bộ nhớ) và thời gian thực hiện nó. Thông thường, khi nói đến sự phức tạp của thuật toán, người ta chỉ muốn đề cập đến mức độ tiêu tốn thời gian của nó. Khi đó người ta đánh giá thuật toán dựa trên một hàm gọi là hàm phức tạp f: N ->N mà f(n) là thời gian thực hiện thuật toán trên dữ liệu vào có kích cỡ là n, tính cho trường hợp xấu nhất. Giả sử ta có đoạn code:

sum = 0;
for (int i = 0; i < n; i++)
{
    sum = sum + i;
}

Tổng số phép tính được thực hiện trong vòng for là n phép tính, vì vậy độ phức tạp là O(n). Ví dụ thứ hai:

sum = 0;
for (int i = 0; i < n; i++)
{
    for (int j = 0; i < m; i++)
    {
        sum = sum + i + j;
    }
}

Tổng số phép tính được thực hiện ở đây là n.m phép tính, vì vậy độ phức tạp là O(n.m). Lưu ý: O(n) = O(kn) hay O(n^2) = O(kn^2), ... hay nói cách khác, hệ số không quan trọng. Một cách khác để tính được độ phức tạp của thuật toán là sử dụng Định lý thợ (Master Theorem), bạn có thể tìm hiểu thêm về vấn đề này.

• Một thuật toán tốt là một thuật toán có độ phức tạp của hàm phức tạp nhỏ, trên thực tế, độ phức tạp của các hàm thường được đánh giá như sau: O(log(n)) < O(n) < O(n.log(n)) < O(n^2) < O(n^3) < O(n^4) < ... < O(2^n) < O(n!) < O(n^n)

Hi vọng bình luận của mình có thể giúp bạn hiểu được cơ bản về độ phức tạp của thuật toán.

Bạn tham khảo thử một số bài viết này xem sao:

https://brilliant.org/wiki/big-o-notation

https://brilliant.org/practice/big-o-notation

Ngoài Big-O (big 0) thì còn có Big-$\Omega$ (big omega), Big-$\Theta $ (big theta) bạn có thể tìm hiểu thêm nếu thích

Nếu bạn cần thêm tài liệu tiếng Anh thì mình thấy trang này cũng giải thích khá rõ và có thêm ví dụ đi kèm cho từng trường hợp

https://github.com/raywenderlich/swift-algorithm-club/blob/master/Big-O Notation.markdown