Tản mạn về Big O

Hi mọi người, mình là Hiếu, 1 developer cùi "bép" ở 1 công ty startup nọ. Mình rất đam mê giải thuật (nhưng mình khá cùi) nên mình đã làm khá nhiều dạng bài. Khi vừa bắt đầu tập tành, mình lúc nào cũng thoả mãn với việc mình giải ra 1 bài toán với tư duy logic ( nghe khá nguy hiểm ), nhưng vào lúc đó mình luôn luôn chỉ code 1 cách mù quáng, code cho ra.

Ví dụ như ai đó bảo mình tìm phần tử trùng trong 1 mảng n phần tử với n-1 phần tử khác nhau chẳng hạn. Mình sẽ vò đầu bứt tóc, nhăn nhó, suy tư để viết ra 1 thứ như thế này:

	function findDuplicate(arr){
		for(var i = 0; i < arr.length-1; i++)
			for(var j = i + 1; j < arr.length; j++)
				if(arr[i] == arr[j])
					return arr[i];
	}

Đoạn code trên chắc hẳn ai đọc cũng hiểu nhể 😩. Mình dùng 2 vòng lặp vòng đầu tiên chạy từ 0 -> length-1 của array, vòng 2 thì chạy phần tử i+1 -> length của array, yeahhhhh mình sẽ so sánh điều kiện nếu nó arr[i] == arr[j] thì đó là số mình tìm. WooHoo cuối cùng cũng giải được 1 bài toán khó, quẩy thôi nào 🕶️. Bài này tới đây là hết nhé.

Haha đùa thôi, đoạn code này sử dụng 2 vòng lặp lồng vào nhau và mỗi vòng lặp chạy n phần tử ( đừng bắt bẻ chỗ n-1 hay n mà 😟 ), nghĩa là nó sẽ duyệt qua n^2 phần tử. Hổng biết đề cho mình 1 mảng 3 phần tử hay 300 triệu phần tử nữa, lo quá lỡ chạy cái này đứng máy thì sao huhu. Không sao đã có Big O. Vậy Big O là gì ?

Big O là gì ?

Khái niệm về cái này khá là vờ lờ.

Big O là một ký hiệu toán học mô tả hành vi giới hạn của hàm khi đối số có xu hướng hướng tới một giá trị cụ thể hoặc vô cùng.

---

Mình dịch từ Wiki chứ mình cũng méo hiểu cái đống quote ở trên đâu hihi. Khó hiểu quá, thử tìm 1 vấn đề trong cuộc sống xem sao 👽

Imtermet và chim bồ câu:

Ngày xửa ngày xưa, thời ăn lông ở lỗ người tối cổ, họ đã phát mình ra 1 hệ thống mạng gọi là Imtermet, nhưng tốc độ thì chậm vô cùng. Người chồng thì đang chuẩn bị truyền 1 số file quan trọng từ nhà tới công ty, mà những file đó khá nặng nên mất hơn 4 ngày để số file đó có thể đi theo đường Imtermet từ nhà ông ta đến công ty. Nên ông ta quyết định sẽ chép file đó sang 1 ổ đĩa nhỏ rồi buộc vào chú chim pidgeot ( pokémon nhé ) rồi cho chú chim giúp mình gửi ổ đĩa đó, thật bất ngờ chỉ mất vài giờ để họ có thể gửi 1 số lượng file khổng lồ như vậy, chuyện như đùa 😥. Đó cũng là 1 ví dụ so sánh giữa độ phức tập O(N) và O(1).

Ô kê vậy thì có gì khác biệt giữa chúng?

+ Imtermet:

Ở đây kích thước file chính là O(N), như file 2Gb hay 200Tb, và có thể tính thêm tốc độ đường truyền, cáp đồng hay cáp cỏ, bla bla.

+ Chim:

Chính là đại lượng không đổi có thể xem là đại lượng không đổi có thể là O(1) cũng có thể là O(99) tùy vào trường hợp chú chim có đi theo tiếng gọi của chim mái hay không 💘.

Big(O) không dùng để làm công thức tính thời gian chạy

Bởi vì thôi gian chạy của 1 chương trình phụ thuộc vào rất nhiều yếu tố như:

• Máy tính của bạn là siêu máy tính của IBM hay là cái máy tính được sản xuất từ đời Tống, thì sẽ có những tốc độ xử lý khác nhau.
• Bạn code bằng ngôn ngữ gì ? Vì mỗi ngôn ngữ có những cơ chế thông dịch hoặc phiên dịch khác nhau, nên nó sẽ cho ra những hiệu suất khác nhau.
• Space complexity là độ phức tạp bộ nhớ.
• Nhiều nhiều lắm kể mệt quá

Vì vậy:

Mục đích của Big O là để so sánh nhanh chậm của thuật toán chứ không dùng để tính chính xác thời gian chạy của thuật toán.

---

Best Case, Worst Case

Vấn đề nè: Giả sử bạn đang làm HR cho 1 công ty to bự :neutral_face: và đang tìm 1 số lượng lớn developer. Thực tế có rất nhiều cách để bạn có thể làm đúng hem ? Ví dụ 1 số hen.

• Bạn sử dụng Facebook tìm 1 group random nào đó và đi nhắn tin cho từng người trong danh sách đó để hỏi họ có phải developer không để còn mà tuyển. Nếu đúng hoặc không bạn lại tiếp tục hỏi người đó để xem họ có biết thêm ai khác không, và tiếp tục nhắn cho những người đó. Vậy mỗi khi hỏi 1 người xong bạn sẽ lại nhận thêm 1 list dài những người khác. Vậy độ phức tạp ở đây là O(N^2**) phải không** 😟.
• Vẫn tìm người trong group nào đó như trên. Nhưng lần này bạn hỏi họ có phải developer không Yes/No và không hỏi thêm những thông tin khác. Có thể bạn sẽ tìm ra 1 vài người ngay trong những người đầu tiên, có thể không. Làm vậy có nghĩa là bạn phải chạy tuần tự từ người đầu tiên tới người cuối cùng của nhóm phải hông 😪. Vậy độ phức tạp ở đây là O(N).
• Lần này bạn sử dụng Linkedin để sử dụng chức năng search filter của nó và tìm kiếm developer. Hihi giờ sẽ ra 1 list gồm những anh toàn là developer cao to đen hôi nhé. rồi lại dùng filter để lọc ra các anh Java developer lọc nhiều lần theo yêu cầu bạn đưa ra. Như thế mỗi lần sử dụng bộ lọc nó sẽ giúp bạn giảm đi 1 thành phần đáng kể những người không phù hợp. Trường hợp này độ phức tạp sẽ là O(logn)

Thực tế ngoài Big O còn có các Big khác nữa ( ớ ờ nhức đầu quá T_T ) đó nha:

1. Big(O): là trường hợp tệ nhất của thuật toán 😢
2. Big Omega (Ω): Cái này ngon lắm. Nó là trường hợp tốt nhất. Ví dụ như tìm số điện thoại trong danh bạ thì người cần tìm sẽ là người đầu tiên chẳng hạn.
3. Big Theta (Θ): Big Theta thì bao gồm luôn cả 2 thằng kia 😕

Nhiếu thứ quá à @@. Sau đây chính là cách tính Big(O)

Quy tắc bỏ hằng số

Bỏ hằng số ? Bỏ sao, sao bỏ ?

Bỏ hằng số nghĩa là không cần biết bài toán của bạn là O(93N) hay là O(7749N) thì nó cũng là O(N).

Ủa kỳ vậy ?

Vì là thứ 1 những hằng số này sẽ không đáng kể. Thí dụ bạn cướp nhà bank thì bạn sẽ chụp 10 tờ 100$ hay 1 cục kim cương 😘, chứ mình là mình không dám cướp hihi. Thứ 2 là ngày đầu tuần... Haha, thứ 2 là vì ở trên mình có nói Big(O) sinh ra là để mô tả độ phức tạp của thuật toán chứ không dùng để tính chính xác bao nhiêu tiếng ( thuật toán chạy bằng tiếng là nát bét luôn ) để thuật toán đó chạy.

Quy tắc lấy công, nhân

Dễ hiểu thôi ví dụ sáng mẹ cho N bác Hồ đồng trưa mẹ lại cho M bác hồ đồng hỏi bé có nhiêu tiền ?

Sum = N + M

( thực ra bé ăn hết rồi )

	function print(arr){
		for(let i = 0; i < arr.length; i++) // O(N)
			console.log(arrDup[i]);
		if(arr.length > 3) // O(1)
			console.log("Hieu cute"); 
	}

Ở đoạn code trên thì mình sẽ chia 2 phần là phần for sẽ là O(N) và phần if chỉ in ra màn hình 1 giá trị nên là O(1)

Áp dụng quy tắc cộng ta có ( sao giống cấp 2 quá ):

O(1) + O(N) = O(1+N)

Nhân cũng giống vậy.

Quy tắc lấy max

Giống như quy tắc bỏ hằng vậy thôi, chúng ta sẽ giữ lại đại lượng lớn nhất của biểu thức.

Code nè

	function printAllDuplicate(arr){
		let arrDup = [];
		for(let i = 0; i < arr.length-1; i++)
			for(let j = i + 1; j < arr.length; j++)
				if(arr[i] == arr[j])
					arrDup.push(arr[i]);
		for(let i = 0; i < arrDup.length; i++)
			console.log(arrDup[i]);
	}

Giả bộ xài lại code ở trên hihi, đoạn này là cho 1 array có tùm lum số trùng hết, xong in ra mấy số trùng ( cái này ko phải cách tốt nhất nhưng mình sẽ dùng cái này làm ví dụ cho dễ ). Vậy đầu tiên cái for lồng nhau là O(N^2**)** như mình đã nói ở trên và 1 vòng lặp in sẽ là O(N) đúng không nè. vậy thì độ phức tạp sau áp dụng lấy max sẽ là O(N^2**)**

Lại áp dụng quy tắc cộng nheeee để tính nha:

O(N^2) + O(N) = O(N^2 + N) = O(N^2)

Nice nhaa

Kết

Big(O) là cách bạn dùng để tính độ phức tạp của 1 thuật toán. Nó có những cách thức và công thức để có thể tính ra được. Với mình thì nó khá là cần thiết cho 1 lập trình viên. Nhiều ông sẽ nói "tao code chục năm rồi mà có thèm quan tâm cái này". Chính xác là như vậy đó nhưng nếu code có thể tối ưu, chạy 1 cách khoa học nhất thì mình tin chắc performance sẽ ngon lành và có thể sẽ tìm được 1 số giới điểm chưa tối ưu khi giải quyết thuật toán chẳng hạn.

Bái bai