Tìm hiểu độ phức tạp thời gian (Big O) cho người mới chi tiết
Tìm hiểu Big O cho người mới chi tiết
Khi
chúng ta làm việc với thuật toán, chúng ta cần đánh giá chúng xem thuật toán
chúng ta đã tốt chưa. Một câu hỏi được đặt ra như sau:
“Thời
gian mà chương trình (thuật toán) chúng ta chạy là bao lâu?”
Câu
hỏi này thật sự khá rắc rối, vì nó không chỉ liên quan đến thuật toán mà còn
liên quan đến ngôn ngữ bạn viết, cũng như vi xử lý của bạn. Vì vậy, chúng ta cần
một câu hỏi khác dễ trả lời hơn.
“Khả
năng phát triển (lâu hoặc nhanh) của
chương trình như thế nào”
Ví
dụ đơn giản như ta có một chuỗi n số nguyên, và thực hiện phép toán cộng. Việc
làm của chúng ta là chạy từ 1 đến n, và cộng từng số nguyên trong chuỗi lại với
nhau. Với n càng lớn, thì việc chạy càng lâu. Vậy ta có thể hiểu rằng, khả năng
phát triển chương trình càng lớn khi input càng tăng. (Phát triển ở đây hiểu là phát triển về thời gian)
Việc
xem xét khả năng phát triển của chương trình dựa vào input là một cách hay để
đánh giá thuật toán đó!
Để
cụ thể hơn, chúng ta đi vào ví dụ sau!
Chúng
ta có một chương trình tính tổng với input có chiều dài lần lượt là 1, 2, 3, 4,
5, 10, 20, 30. Chúng ta sẽ thử đo thời gian với từng trường hợp xem như thế nào.
(Tất nhiên với mỗi ngôn ngữ và vi xử lý
thì thời gian khác nhau, tuy nhiên cái chúng ta quan tâm ở đây là cách chương
trình phát triển)
Ta
thử đọc hình vẽ xem sao! Với một phần tử thì ta có thời gian chạy là 0.25 micro
giây, với 30 phần tử thì thời gian chạy khoảng 1.25 micro giây. Nhìn vào đồ thị,
ta thấy rằng mỗi khi số phần tử tăng lên, thời gian cũng tăng lên theo một đường
thẳng. Ta gọi time complexity này là linear time. (Time complexity: Một thể hiện trên đồ thị sự phát triển của chương
trình khi input tăng)
Ngoài
ra chúng ta còn mội vài loại time complexity: Constant time và quadratic time.
Constant time
Constant
time dùng để thể hiện rằng với số lượng phần tử input dẫu có tăng lên bao nhiêu
thì thời gian thực thi chương trình vẫn sẽ không đổi.
Quadratic time
Quadratic
time dùng để thể hiện rằng khi số lượng input tăng thì thời gian tăng theo cấp
bình phương – giống linear nhưng thời gian tăng càng ngày càng lớn.
Ok.
Bây giờ chúng ta mong muốn thể hiện chúng theo cách của số học, như là các ký
hiệu chẳng hạn. Vậy có cách nào không? Đây là lúc mà khái niệm Big O ra đời.
Đây là cách ký hiệu của Big O
Linear time – O(n) (Cách
đọc: “big-oh of n” hoặc đôi khi “oh of n”)
Constant time – O(1)
Quadratic time – O(n2)
Ta
có thể thấy rằng, việc thay đổi giá trị bên trong ngoặc đơn sẽ tạo ra những loại
time complixity khác nhau. Nhưng làm sao chúng ta biết thay đổi thế nào thì ra
loại tương ứng? Chúng ta có một cách để tìm ra (tuy nó không phải là cách chính
thống – không áp dụng được với tất cả các Big O, tuy nhiên nó sẽ hữu dụng).
Chúng ta sẽ thực hiện theo 2 bước sau:
1.
Tìm
một số hạng có khả năng phát triển cao nhất
2.
Lấy
đi hệ số của nó
Lấy
ví dụ về Linear time. Đồ thị của nó có dạng T = a*n + b (trong đó T là biến chỉ
thời gian, n là biến chỉ số lượng phần tử input, a và b là các hệ số).
Bước 1:
Ta thấy rằng an và b là 2 số hạng. Xét theo sự phát triển thì a*n sẽ phát triển
hơn b khi n tăng lên (Vì b là hằng số nên không đổi khi n tăng). Ta chọn a*n
Bước 2:
Lấy đi hệ số của a*n là a, ta được n
Thế
là ta ký hiệu là O(n)
Trường
hợp Constant time và Quadratic time các bạn có thể tự tính toán
(Gợi ý:
Phương trình của Constant time có dạng
T = a
Phương trình của Quadratic time có dạng
T = a*n2 + b*n + c)
Big
O thực sự không phụ thuộc vào môi trường mà nó đang chạy. Giả sử cùng một thuật
toán nhưng ta sử dụng một máy tính có tốc độ xử lý cao hơn, ngôn ngữ chạy nhanh
hơn,.... Thế thì nó sẽ trông như thế này.
Ta
thấy rằng ở đường thẳng màu đỏ, tuy tốc độ xử lý cao hơn, nhưng nó vẫn thể hiện
dưới dạng một phương trình đường thẳng, vẫn thể hiện bằng T = a*n + b. Tuy a hoặc
b có thể lớn hơn một chút, tuy nhiên nếu làm theo 2 cách xác định Big O trên,
ta vẫn thu được O(n). Chính vì thế, đây là chứng minh cho việc Big O không phụ
thuộc vào môi trường thực thi.
Chúng
ta sử dụng Big O để đánh giá 2 thuật toán. Giả sử với cùng một thuật toán, một
bên có time complexity là O(1), một bên là O(n). Nếu n đủ lớn thì thời gian sẽ
khá lâu so với O(1) (trong thực tế chúng
ta ít khi xử lý lượng số liệu ít, nên n thường hay khá lớn). Vì thế chúng
ta sẽ đặt điểm cộng cho O(1). Tất nhiên, không phải cứ O(1) với O(n) thì ta sẽ
chọn O(1), vì đó chỉ là một nhân tố trong số những nhân tố mà ta xét khi lựa chọn
thuật toán: bộ nhớ, tính dễ dàng trong việc đọc code,... Nhưng đó vẫn là một
nhân tố chúng ta nên xem xét.
Như
từ nãy đến giờ chúng ta nói, ta có thể xác định được một Big O bằng cách đo đạc
thời gian, vẽ đồ thị, viết phương trình rồi xác định ký hiệu Big O. Tuy nhiên
cách làm này mất khá nhiều thời gian để thử nghiệm. Vậy thì, có cách nào để xác
định Big O mà tiết kiệm thời gian hơn không?
Bây
giờ, chúng ta hãy cùng đi vào ví dụ sau. Ví
dụ 1:
function(given_array){
//given_array là mảng một chiều
total
= 0;
return
total;
}
Ta
sẽ thử xác định Big O của từng dòng
total
= 0; O(1)
return
total; O(1)
Cả
hai đều là O(1) vì dù số phần tử input có tăng lên bao nhiêu, thì thời gian thực
thi của hai dòng lệnh trên vẫn giữ nguyên như cũ. Dễ nhìn thấy, cả hai dòng lệnh
đều không tác động đến given_array.
Như
thế thì ta sẽ tính tổng bằng cách lập phương trình sau T = O(1) + O(1)
Ta
biết rằng bản chất của O(1) là một hằng số (constant). Vì thế ta sẽ đặt c1
và c2 là hai hằng số tương ứng với hai O(1) phía trên. Như thế ta được
T = c1 + c2
Hằng
số + hằng số = hằng số. Ta đặt c3 là tổng của c1 và c2,
và cũng là một hằng số. Vậy thì
T = c3
Ta
thấy nó giống với dạng T = a, là dạng O(1) mà ta đã nói ở phía trên. Có thể một
số bạn chưa thử tự tính toán ở phía trên, thế nên mình sẽ tính luôn.
T = c3 = c3 * 1 = O(1) (loại hệ
số c3)
Lưu ý nhỏ: Ta có thể đặt O(2) O(100)
O(99999) tùy thích vì theo nguyên tắc ta có thể làm như thế này c3 =
c3 * 1/100 * 100 và coi c3 * 1/100 là hệ số cần loại bỏ.
Tuy nhiên thông thường chúng ta chỉ sử dụng O(1)
Với
một ví dụ khác. Ví dụ 2:
function(given_array){
total
= 0;
for(each
value in given_array){
total += value;
}
return
value;
}
Ta
phân tích big O từng dòng như sau
total
= 0; O(1)
total
+= value; O(1)
return
value; O(1)
Với
3 dòng này, như ta thấy, thì Big O của nó chính là O(1). Thế nhưng ta lưu ý rằng,
total += value thực hiện lặp lại n lần (n là số phần tử input) vì thế nên cả đoạn
for(){} sẽ là n*O(1)
Lưu ý: Với for từ 1 tới một hằng số
hay biến không liên quan đến số lượng phần tử input thì ta có thể xem như là
a*O(1) = O(1) với a là hằng số
Như
vậy, ta có phương trình sau
T = O(1) + n * O(1) + O(1)
Ta
biết rằng O(1) + O(1) là một hằng số, vậy nên ta sẽ gom chúng thành một hằng số
b
O(1)
trong n * O(1) sẽ đặt hằng số a
Như
thế ta có:
T = a*n + b
Ta
tiếp tục thực hiện hai bước như đã đề cập ở phía trên để tìm ra Big O. Các bạn
có thể tự làm thử. Hoặc ở đây, để đơn giản, ta có thể thấy rằng dạng phương
trình này giống với phương trình kiểu time complexity là linear time. Chính vì
thế, Big O của nó sẽ là O(n).
Thêm
một ví dụ nữa để chúng ta hiểu hơn. Ví dụ
3.
Lần
này, given_array của chúng ta không phải là mảng một chiều nữa, mà là mảng hai chiều.
function(given_array){
total = 0;
for(each
row in array){
for(each
value in row){
total += value;
}
}
return
total;
}
Đây
là bài toán tính tổng một mảng 2 chiều của ma trận vuông. Chúng ta sẽ duyệt từng
dòng, với mỗi dòng thì chúng ta sẽ duyệt từng giá trị và tính tổng.
total
= 0; O(1)
for(each
row in array){ n times
for(each
value in row){ n times
total += value; O(1)
}
}
return
total; O(1)
Vì
2 vòng for của chúng ta duyệt n*n phần tử (tương ứng với ma trận vuông n*n),
cho nên ở đây sẽ là n2*O(1). Tổng lại ta có phương trình như sau:
T = O(1) + n2*O(1) + O(1)
Với
O(1) + O(1) là một hằng số, ta sẽ đặt b là hằng số cho nhóm này, a là hằng số
cho O(1) thuộc n2*O(1). Như vậy ta có
T = a*n2 + b
Theo
2 bước ta thực hiện, ta sẽ chọn a*n2, loại a và Big O của phương
trình trên sẽ là O(n2)
Quick:
Sẽ như thế nào nếu có hai lần double for? Ví dụ như sau:
function(given_array){
total = 0;
for(each
row in array){
for(each
value in row){
total += value;
}
}
for(each
row in array){
for(each
value in row){
total += value;
}
}
return
total;
}
Như
vậy thì chúng ta sẽ có T = O(2*n2) = O(n2). Số 2 thể hiện
việc lặp lại double for 2 lần. Nhưng vì sao lại ra O(n2). Chúng ta
cùng xem nhé
O(2*n2)
= 2*n2*a + b*n + c (Vì đây là dạng quaratid time nên mình triển khai
nó sang dạng này)
Ta
sẽ giữ lại số hạng 2*n2*a vì đây là số hạng có mức độ phát triển
nhanh nhất
Ta
sẽ coi 2*a là một hệ số, tạm gọi là k. Như vậy ta có
2*n2*a
= 2*a* n2
Ta
loại hệ số 2*a ra
Vậy
Big O sẽ là O(n2)
Còn
O(nlogn) cũng như một số dạng khác có thể chúng ta sẽ tìm hiểu sau!
Lời
kết: Sau một thời gian chưa viết blog thì
nay mình lại viết dữ dằn hơn. Thêm cả mình rất chân thành cảm ơn kênh youtube
CS Dojo đã có một bài dạy rất cụ thể. Mình dựa vào phần lớn bài dạy đó viết bài
viết này. Xin cảm ơn!
Nội dung bài viết thuộc về Lê Công Diễn.
Người viết: Lê
Công Diễn
Mang đi nhớ ghi nguồn
Nhận xét
Đăng nhận xét