GIẢI THÍCH MỘT SỐ DẠNG BIG O: O(LOGN)

GIẢI THÍCH MỘT SỐ DẠNG BIG O: O(LOGN)

Đây là một độ phức tạp điển hình, có rất nhiều trong các dạng cấu trúc dữ liệu và giải thuật cơ bản. Nắm được cách tính độ phức tạp O(logn) của các thuật toán sẽ giúp bạn tự tin hơn được 50% trong hầu hết các dạng big O. Trước khi bắt đầu bài viết, mình muốn các bạn cần tìm hiểu qua về hai bài viết cũ của mình về Big O là gì và cách tính độ phức tạp của Big O cho hàm đệ quy. Bạn tham khảo qua hai bài viết sau:

Bài viết 1: Tìm hiểu độ phức tạp thời gian (Big O) cho người mới chi tiết

Bài viết 2: Tính toán big O cho hàm đệ quy

Nếu không nắm cơ bản về big O thì đọc bài này sẽ rối nhé.

Trước khi vào bài mình sẽ mục lục hóa lại bài viết để cho các bạn dễ hình dung

1.    Giải thích về log - Giải thích về log2

2.    Giải thích về cách tính O(logn)

3.    Tiếp cận các bài toán tìm kiếm với O(logn) và các big O khác.

4.    Tiếp cận bài toán về O(logn)

Bắt đầu thôi!

1.    Giải thích về log - Giải thích về log2

Đầu tiên ta hiểu rằng số mũ là số chỉ số lượng thừa số nhân với nhau, ví dụ

3¹ = 3

3² = 3*3 (số 3 nhân với nhau 2 lần)

3³ = 3*3*3 (số 3 nhân với nhau 3 lần)

….

3ⁿ = 3*3*….*3 (số 3 nhân với nhau n lần)

 

Như vậy, đặt ra bài toán sau:

Tìm giá trị x trong trường hợp

3^x = 27

Nghĩa là ta đang muốn tìm kiếm rằng số 3 nhân với nhau bao nhiêu lần để trở thành số 27. Ta viết lại bài toán này thành:

log₃(27)

Như vậy, hàm log là hàm dùng để tìm hàm mũ, hay nói dễ hiểu hơn là tìm xem số 3 phải nhân với chính nó bao nhiêu lần để trở thành số 27.

Ta có dạng tổng quát như sau

log_a(b)

Ta đọc là logarit của b với cơ số a (Tiếng Anh: logarithm of “b” to the base “a”). Hiểu nôm na là số a nhân với chính nó bao nhiêu lần để trở thành số b.

 

Ở toán học, khi người ta ghi log mà không sử dụng base (ví dụ: log 27) thì có nghĩa là họ sử dụng cơ số e, với e xấp xỉ =  2.71828 (log 27 = log_e(27) ). Còn trong lập trình xét về trường hợp tính độ phức tạp, thì người ta sử dụng cơ số 2 (log 27 = log₂(27)) vì đây là trường hợp độ phức tạp xuất hiện phổ biến nhất.

Như vậy, bạn có thể hiểu tiêu đề bài viết rằng, khi chúng ta viết O(logn) cũng có nghĩa là O(log₂n).

Trước khi đi vào bài toán về O(logn), ta cùng tìm hiểu lại một chút về big O.

Giả sử ta có các đồ thị thời gian của các bài toán như sau

(Hình này chưa thể hiện chính xác số liệu, chỉ mang tính minh họa)

Như các bạn biết rằng, khi lập trình, chúng ta cực kỳ quan tâm về tỉ lệ giữa số lượng phần tử chúng ta đưa vào và thời gian để thực hiện chúng. Ví dụ, khi hệ thống của bạn có 10 user cùng đăng nhập, 20 user cùng đăng nhập, 100 user cùng đăng nhập, thì thời gian thực hiện là bao lâu.

Câu hỏi về “Thời gian thực hiện là bao lâu này” khá là mơ hồ, vì rất khó để vẽ chính xác biểu đồ thời gian như hình vẽ đối với từng loại bài toán. Vì tốc độ nhanh hay chậm phụ thuộc vào rất nhiều yếu tố tùy vào từng môi trường thực thi, ngôn ngữ lập trình, từng máy tính, kết nối mạng,… Tuy nhiên, có một điểm chung rằng các đồ thị này tăng tuyến tính theo thời gian. Ta gọi chung sự tăng tuyến tính này là O(n). Bản chất của sự tuyến tính trong phương trình y=ax+b không phụ thuộc vào a, b nên ta thường không quan tâm số hạng của chúng.

Cho x = n, ta gọi tên bằng O(y) = O(f(n)) = O(n). Đây là dạng big O phổ biến các bạn hay nhìn thấy. Khi nhìn big O này, các bạn hiểu rằng số lượng phần tử càng tăng, thì thời gian càng tăng dần đều lên. Đây là dạng độ phức tạp thường xuất hiện nhiều trong duyệt mảng tuyến tính.

 

(Vẫn lưu ý là hình minh họa)

Với trường hợp này tương tự ta loại bỏ các hằng số (lý do đã nêu trên) sẽ thu được là y = x². Với x = n, ta gọi tên O(y) = O(f(n)) = O(n²). Có thể hiểu rằng các thuật toán có dạng O(n²), thì với số lượng phần tử càng tăng, thời gian sẽ tăng lên cấp bình phương. Bạn có thể nhìn lại hình phía trên để hiểu mức độ khủng của các đồ thị hàm mũ khi số lượng phần tử tăng dần.

Các thuật toán với O(n²) thường xuất hiện đối với hai vòng lặp lồng nhau khi phải thực hiện lặp n lần *  n vòng lặp con (n*n = n²) (tuy nhiên không phải cứ hai vòng lặp lồng nhau là O(n²) mà chỉ đang nói trường hợp chung). Do nguồn dữ liệu hiện nay cực kỳ khổng lồ cộng với thời gian chạy tăng “đột biến” khi n rất lớn, nên thông thường các thuật toán sẽ cố gắng hạn chế tối đa sự xuất hiện của các dạng độ phức tạp mũ như O(n²), O(n³),…

Bây giờ, chúng ta cùng tìm hiểu về O(logn) nhé.

 

1.     Giải thích về cách tính O(logn)

 

Như đã giải thích ở trên, log n có nghĩa là log₂n, nghĩa số 2 phải nhân với nhau logn lần để thành số n. Hoặc bạn có thể hiểu ngược lại rằng, số n chia cho 2 logn lần để thành số 1 (*). Mình sẽ vẽ hình dung hai cách hiểu bản chất log n như sau.

Với cách 1, ta bắt đầu từ số 2, và nhân với nhau logn = 3 lần để được số 8

Với cách 2, ta bắt đầu từ số 8, và chia đôi nó logn = 3 lần để trở về số 1.

Cách hiểu thứ hai được sử dụng phổ biến hơn để tìm kiếm O(logn) của bài toán. Nếu có bài toán bảo rằng: “ Cho một số n, mỗi lần chạy hãy chia số n đó cho 2, cho đến khi n = 1” thì chắc chắn độ phức tạp của thuật toán là O(logn)

Ta thấy rằng chương trình có độ phức tạp là O(logn) vì mỗi lần chạy nó sẽ chia đôi giá trị n cho tới khi bằng 1 theo như cách 2 đã nêu trên.

Và đây là đồ thị đối với log n (lưu ý thêm một lần nữa là log n chính là log₂n trong big O nhé)

Với trục tung là thời gian, trục hoành là số n. Ta có thể thấy rằng càng có nhiều phần tử thì thời gian phát triển càng chậm. Ví dụ về sự tăng trưởng n như sau:

-        n = 8 thì log(n) = 3

-        n = 16 thì log(n) = 4

-        n = 32 thì log(n) = 5

-        n = 64 thì log(n) = 6

-        n = 128 thì log(n) = 7

-        n = 256 thì log(n) = 8

-        …

Bạn thấy rằng số n tăng càng ngày càng nhanh nhưng log n tăng theo rất chậm. Chứng tỏ rằng độ phức tạp O(logn) là độ phức tạp tuyệt vời hơn hẳn cả O(n²) và kể cả O(n) đối với trường hợp n là một con số cực lớn.  

Như vậy, ta đã hiểu rõ bản chất của O(logn) rồi. Bây giờ ta sẽ xem xét các bài toán cụ thể và cách tính O(logn) một cách nhanh gọn mà không cần phải xét từng dòng code nhé.

1.    Tiếp cận các bài toán tìm kiếm với O(logn) và các big O khác.

Ở mục này, khuyến khích bạn nên tự xem trước một số thuật toán sắp xếp nhé. Ở đây mình lựa chọn hai thuật toán để so sánh về độ phức tạp, đó là Selection Sort và Quick Sort (Các thuật toán đều sắp xếp theo thứ tự tăng dần)

1.1  Selection Sort.

Thuật toán Selection Sort tiến hành mỗi lần sẽ duyệt toàn bộ mảng để tìm phần tử nhỏ nhất đưa lên vị trí đầu. Phần tử nhỏ thứ hai sẽ nằm ở vị trí thứ hai của mảng. (Bạn tự tìm hiểu thêm Selection Sort nhé)

Đây là mã giả của selection sort, bạn thấy rằng có hai vòng for và vòng for ngoài duyệt n lần, mỗi vòng for trong duyệt từ j +1 đến n lần. Như vậy tổng số lần duyệt sẽ là

y = f(n) = n + n-1 + n-2 + … + 2

=  (n(n+1)/2) - 1 [Áp dụng công thức tính tổng n số tự nhiên]

= n² + n [Bỏ qua các hệ số]

ð O(y) = O(f(n)) = O(n²) [Chọn biến số có độ biến thiên lớn nhất]

Như vậy, độ phức tạp của Selection Sort là O(n²). Độ phức tạp này tương tự đối với Bubble Sort sử dụng hai vòng lặp for với vòng lặp thứ hai duyệt từ j+1 đến n lần. Đây tất nhiên không phải là một thuật toán sắp xếp tối ưu bạn nên sử dụng đối với lượng data khổng lồ, vì nó có độ phức tạp rất tệ.

1.1  Quick Sort

Chính vì các thuật toán sắp xếp cổ điển trên có độ phức tạp rất tệ O(n²) dẫn đến khó xử lý các bài toán có lượng dữ liệu lớn. Quick Sort ra đời để giải quyết vấn đề này.

Mấu chốt của thuật toán Quick sort là chọn một số trong mảng (gọi là pivot) và sắp xếp làm sao để cho các phần tử bên trái nhỏ hơn pivot, các phần tử bên phải lớn hơn pivot. Sau khi hoàn thành thì vị trí pivot là vị trí đúng. Ta cắt mảng ra làm hai phần và mỗi phần đó tiếp tục thực hiện Quick Sort (sử dụng đệ quy). // Cái này các bạn tìm hiểu thêm nhé.

Và đây là mã giả của thuật toán

Ở đây, bạn biết rằng việc lựa chọn pivot ở left, right hay middle cũng như giá trị mảng đưa vào sẽ ảnh hưởng đến tốc độ chạy của chương trình. Ở đây chúng ta xét trường hợp tốt nhất và trường hợp xấu nhất của chương trình.

Với trường hợp tốt nhất, pivot của mảng luôn chia làm hai nửa bằng nhau.

Khi đó, ta sẽ có cây như hình trên. Ta để ý rằng ở trên hình, số tầng của cây là log(n) vì mỗi lần nó sẽ chia cho 2 cho đến khi chỉ còn 1 đơn vị, và cũng như là đối với mỗi tầng, ta đều duyệt qua hết tất cả các ô trên đồ thị. Theo hình, ta lấy độ sâu của cây * thời gian duyệt mỗi cấp = log n * n . Số lần duyệt cũng chính là độ phức tạp của thuật toán là O(nlogn).

Trong trường hợp xấu nhất, pivot của chúng ta chọn luôn nằm ở vị trí điểm đầu hoặc điểm cuối của mảng. Trường hợp này xuất hiện khi gặp mảng đã được sắp xếp từ trước. 

Khi đó, giống với trường hợp của Selection Sort hoặc Bubble Sort, ta duyệt tổng cộng là n + (n-1) + (n-2) + … + 2 thì độ phức tạp sẽ là O(n²).

Có một số kỹ thuật để hạn chế xuất hiện trường hợp xấu nhất như random pivot hoặc kiểm tra trước xem mảng có được sắp xếp hay không. Nhưng tóm lại, độ phức tạp của Quick Sort sẽ dao động trong khoảng O(nlogn) cho đến O(n²). => Có một sự tối ưu rất lớn so với các thuật toán sắp xếp truyền thống.

1.                    4. Tiếp cận bài toán khác về O(logn)

    Nếu các bài toán trên hơi phức tạp để bạn hiểu về O(log n), thì dưới đây là bài toán     quen thuộc để bạn hiểu hơn về O(log n). Đó là bài toán TÌM KIẾM NHỊ PHÂN.

    Tìm kiếm nhị phân là bài toán tìm kiếm một giá trị nằm trong một mảng đã được sắp     xếp từ trước, bằng cách so sánh giá trị cần tìm với phần tử ở giữa cộng với chia đôi     mảng để thu hẹp phạm vi tìm kiếm dần // Cái này các bạn tìm hiểu thêm nhé.

 

Bạn thấy rằng, trong trường hợp xấu nhất, với ban đầu là n phần tử, mỗi lần mảng sẽ chia nửa ra cho đến khi bằng 1.   

Ở đây bạn để ý rằng cây có độ sâu là logn, và mỗi node nó chỉ thực hiện hằng số lần tác vụ (ở đây mình chọn 1) vì nó không duyệt qua các phần tử trong mảng mà chỉ so sánh phần tử tìm kiếm với phần tử ở giữa. Như vậy, theo như trên ta có ta lấy độ sâu của cây * thời gian duyệt mỗi cấp = log n * 1 . Như vậy, độ phức tạp trong tìm kiếm cây nhị phân là O(logn). Độ phức tạp này tối ưu hơn rất nhiều so với tìm kiếm thông thường khi mà phải duyệt hết toàn bộ mảng với độ phức tạp O(n).

 

Kết luận: Như vậy, thông qua bài blog này ta đã hiểu rõ hơn về độ phức tạp O(logn). Đây là độ phức tạp tối ưu hơn cả O(n) và xuất hiện rất phổ biến trong một số bài toán có thể mô phỏng dưới dạng cây. Cảm ơn các bạn đã đọc bài viết này. Bài viết tuy hơi dài xíu nhưng mình cũng cố gắng viết đảm bảo chất lượng nhất cho người đọc.

 

Nguồn tham khảo:

1.    Big O Notation Series #4: Bí quyết hiểu O (log n)! - YouTube

2.    how n * (n + 1) / 2 does "summation"? : r/askmath

3.    (5) Why is 'quicksort' called 'quicksort'? - Quora

4.    Logarithm Fundamentals | Ep. 6 Lockdown live math - YouTube

5.    Tài liệu nghiên cứu cá nhân

Người viết: Lê Công Diễn

Mang đi nhớ ghi nguồn

 

 

 

 

[Mẹo nhớ công thức tính tổng n số tự nhiên]

Bạn có thể hình dung công thức này bằng hình ảnh sau

Tạo một tam giác với dòng 1 là 1 khối, dòng 2 là 2 khối,… dòng n là n khối. Sau đó tạo một khối tam giác ngược tương tự để tạo ra hình chữ nhật. Diện tích của hình là n*(n+1). Bởi vì mình chỉ lấy nửa hình nên phải n*(n+1)/2