Giải thích big-O

Chào các bác,
Tình hình là em không hiểu lắm phần tính toán Big(O).
Nhờ các bác tư vấn giúp tài liệu nào dùng để đọc và tự học Big(O) ạ.
Xin cám ơn.

Chỉ cần gõ understanding + tên_chủ_đề mà em muốn kiếm lên google là ra
https://www.freecodecamp.org/news/big-o-notation-why-it-matters-and-why-it-doesnt-1674cfa8a23c/#:~:text=In%20plain%20words%2C%20Big%20O,pronounced%20“Big%20O%20squared”.&text=A%20typical%20algorithm%20that%20has,be%20the%20selection%20sort%20algorithm.

5 Likes

Cám ơn bác đã share tài liệu này.
Tuy nhiên, tại đoạn này em chưa hiểu lắm:


Tại sao Inner loop lại tính ra Big O là n(n-1)/2 ạ?
Nhờ bác hướng dẫn thêm.

Đó là công thức tính tổng cấp số cộng em đã dc học ở phổ thông, xem thêm:
https://www.mathsisfun.com/algebra/sequences-sums-arithmetic.html

4 Likes

Em đã đọc và suy ngẫm về link này bác gửi ạ.
https://www.mathsisfun.com/algebra/sequences-sums-arithmetic.html
Tuy nhiên suy nghĩ vẫn chưa ra được tại sao Repeats n-i times mà có thể chuyển thành công thức n(n-1)/2?
Em đang suy nghĩ là phải ra công thức i + (n-i)(n-1) cho vòng lặp này chứ nhỉ?
Nhờ bác giải thích giúp.

Lưu ý i là biến chạy từ 0 đến n-1 :slight_smile: nên nhân vào “như không” vậy là sai.

7 Likes

Giả sử n=100
Lần 1: i=0, vòng nhỏ lặp n=100 lần
Lần 2: i=1, vòng nhỏ lặp 99 lần
Lần 3: i=2, vòng nhỏ lặp 98 lần

Vậy tổng là lặp (100 + 99 + 98 + … + 1)
Cách tính tổng này thì xem ở đây: https://toanhoctuoidep.wordpress.com/2011/10/14/gauss-va-tổng-cac-day-số/

7 Likes

Cám ơn bác em đã hiểu được đoạn (n - i) có công thức là n(n-1)/2 rồi ạ.
Tuy nhiên, trong bài viết này:
https://www.bigocheatsheet.com/
Tại sao Selection Sort có Omega là n^2 aj?


Em nghĩ phải là Ω(n) chứ nhỉ?

Em đọc kỹ 1 chút, sao 2 vòng lặp mà O(n) dc. Với O, Theta & Omega có 3 ý nghĩa khác nhau, phải phân biệt.

5 Likes
  • Big O (O()) describes the upper bound of the complexity.
  • Omega (Ω()) describes the lower bound of the complexity.
    Em hiểu là Big O mô tả cận trên và Omega mô tả cận dưới
    Và selection sort: n^2/2 - n/2 thì không phải cận trên là n^2 và cận dưới là n à bác?
    => Omega phải là n chứ?
1 Like

Bác có thể giải thích rõ hơn được không?

Big O và Big Omega dựa vào lý thuyết tiệm cận của hàm số nên em muốn hiểu nên học lại phần tính lim và khảo sát tính hội tụ (converge) và phân kỳ (diverge) của 1 hàm số.

Trong sách Algorithm Design manual 2nd edition, trang 70 có ghi n! >> c^n >> n^3 ? n^2 >> n >> sqrt(n) >> log^2(n) >> logn >> a(n) >> 1
Với dấu >> là độ tăng nhanh (increase rate) của 1 hàm số khi n chạy đến vô cùng.
Vậy n^2/2 - n/2 thì sẽ chỉ còn phải xét n^2/2 do phần này lớn nhất, nên O và Omega đều là n^2

5 Likes

Cận dưới là Ω(n) như bạn nói cũng được.
Nhưng tìm cận dưới với độ phức tạp càng lớn (nhưng phải nhỏ hơn big-O) thì sẽ càng đánh giá độ phức tạp của giải thuật chính xác hơn -> Tìm chiến thuật giải cũng sẽ tốt hơn

Cứ nghĩ như vầy, nhà bạn có n tầng, bạn muốn tìm lọ muối ở đâu đó trong n tầng. Giả dụ bạn biết đc lọ muốn chỉ ở tối đa tầng 100 -> bạn có thể vui vẻ bỏ qua tầng nào > 100 vì đảm bảo nó ko có lọ muối.
Nhưng 100 tầng vẫn nhiều, và giả dụ bạn biết thêm thông tin là lọ muối ko nằm ở tầng nào nhỏ hơn tầng 90 -> bh range tìm kiếm chỉ còn từ tầng 100 -> 90 (11 tầng)

-> Upper bound càng nhỏ và lower bound càng lớn sẽ giúp bạn ít nhiều thu hẹp khoảng cách để tìm kiếm hoặc theo dõi lại -> Đỡ mất nhiều công sức hơn

Tương tự nếu bạn upper và lower bound của algo, bạn sẽ có chiến thuật giải hiệu quả hơn. Như biết lower bound là Ω(n) và khi nào nó được như vậy, thì có thể ép input về điều kiện hoàn hảo của algo để luôn được O(n)

6 Likes

Thực ra phát biểu theo giải tích còn phát sinh khái niệm mới phức tạp hơn. VD:
|n\sin{n}| = O(n)
Lưu ý là không có \lim \sin{n}.

4 Likes

edit: chắc viết như vậy để thấy là f(n) có đpt nằm giữa best case và worst case, nên viết \Omega kia chắc cũng có lý riêng của họ :V :V

3 Likes

Thực ra 3 trường hợp ứng với 3 hàm T(n) khác nhau, nên dùng như vậy là sai, vì O(f), \Omega(f), \Theta(f) là họ hàm số (biến n), chứ ko phải biến input.

Nhập nhằng giữa worst-case và Big-O là nhầm giữa hàm một biến input và hàm số.

5 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?