Giải thích big-O

Phan_Nhat_Khanh_Huy · July 30, 2020, 5:04am

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.

hitman17528 · July 29, 2020, 7:44am

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.

Phan_Nhat_Khanh_Huy · July 29, 2020, 10:04am

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.

hitman17528 · July 29, 2020, 10:08am

Đó 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

Phan_Nhat_Khanh_Huy · July 30, 2020, 4:52am

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.

rogp10 · July 30, 2020, 6:06am

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

nitro2 · July 30, 2020, 5:47am

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ố/

Phan_Nhat_Khanh_Huy · July 30, 2020, 8:39am

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ỉ?

hitman17528 · July 30, 2020, 8:44am

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.

Phan_Nhat_Khanh_Huy · July 30, 2020, 8:55am

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ứ?

Phan_Nhat_Khanh_Huy · July 30, 2020, 9:22am

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

hitman17528 · July 30, 2020, 10:20am

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

drgnz · July 30, 2020, 10:37am

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)

rogp10 · July 30, 2020, 10:48am

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}.

tntxtnt · July 30, 2020, 12:56pm

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

rogp10 · January 20, 2023, 12:08pm

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ố, chứ không phải hàm có biến input. Worst-case hay không là do input chứ ko phải là do nó có n phần tử, vì input là worst-case khi so cùng độ dài thì thuật toán sẽ chạy lâu nhất.

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ố. Ký pháp Big-O chỉ áp dụng cho hàm số (với hàm nhiều biến thì chỉ áp dụng cho hàm không giảm).