Xin chào tất cả các bạn, mình là Quân, hôm nay mình sẽ viết một bài lý thuyết kèm ví dụ để giải thích cho các bạn một cái nhìn cơ bản và dễ hiểu nhất về thuật toán trong lập trình cũng như độ phức tạp của nó nhé, bài viết này cũng sẽ là tiền đề cho series Xử lý Thuật Toán với ngôn ngữ JavaScript trên kênh youtube Trungquandev Official cũng như blog chính thức này của mình. OK chúng ta cùng bắt đầu bài ngày hôm nay nhé.
“Bài này nằm trong loạt bài Xử lý thuật toán với JavaScript trên trang blog chính thức trungquandev.com“
Những nội dung có trong bài:
- Khái niệm thuật toán và độ phức tạp trong thuật toán là gì?
- Demo duy nhất 2 ví dụ đơn giản và cực kỳ dễ hiểu về độ phức tạp của thuật toán trong lập trình 😀
1. Thuật toán và độ phức tạp trong thuật toán là gì?
Đầu tiên, đã gọi là lý thuyết thì mình sẽ ốp luôn 2 khái niệm của thuật toán cũng như độ phức tạp của thuật toán theo Wikipedia vào đây cho các bạn đọc đã nhé:
Về Thuật Toán – Algorithm
In mathematics and computer science, an algorithm (/ˈælɡərɪðəm/ (listen)) is a finite sequence of well-defined instructions, typically used to solve a class of specific problems or to perform a computation.
https://en.wikipedia.org/wiki/Algorithm
Mình tạm dịch:
Trong lĩnh vực toán học và khoa học máy tính thì một thuật toán được định nghĩa là một tập hợp hữu hạn các hướng dẫn (instructions) được định nghĩa rõ ràng, liên tục và thường được sử dụng để giải quyết một nhóm các vấn đề cụ thể hoặc để thực hiện một phép tính nào đó.
https://trungquandev.com
Về Độ phức tạp của Thuật Toán – (Algorithmic complexity hoặc Time complexity)
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm.
https://en.wikipedia.org/wiki/Time_complexity
Mình tạm dịch tiếp:
Trong lĩnh vực khoa học máy tính thì độ phức tạp của thuật toán sẽ là thước đo một khoảng thời gian mà máy tính phải cần để chạy xong xuôi một thuật toán.
https://trungquandev.com
(Bonus thêm chút từ mình: Chỗ này còn có thể hiểu là “Khoảng thời gian mà máy tính phải cần để hoàn thành một dữ liệu đầu vào có kích thước là n. Chắc đọc đến đây thì một số bạn đã thấy quen quen với mấy kiểu O(n), O(n^2) …vv rồi đúng không?)
OK lý thuyết cơ bản như vậy mình nghĩ là đủ rồi, bạn nào có đam mê với việc nghiên cứu lý thuyết thì có thể đọc thêm ở 2 link wiki mà mình để ở trên nhé, còn đối với mình thì đi vào ví dụ sẽ là cách tiếp cận dễ hiểu nhất, nên ở phần tiếp theo mình sẽ đưa ra ví dụ cụ thể về “Độ Phức Tạp Của Thuật Toán“ cho các bạn dễ hình dung nha.
(Ngoài lề quen thuộc: Cảnh báo này dành cho bất kể trang nào khác mà có ý định copy bài không phải của các bạn thì hãy tôn trọng người viết bài chân chính, tuyệt đối không được xào nấu, chỉnh sửa linh tinh bài viết của mình cụ thể là không được xóa những liên kết (link) cũng như tự ý xóa các câu thoại của mình trong toàn bộ bài viết rồi post lại lên trang của các bạn như kiểu đây là bài của các bạn vậy, nếu tham khảo thì hãy để lại liên kết nguồn rõ ràng từ trang trungquandev, mình sẽ thường xuyên dùng tool để check, và nếu phát hiện ra thì cứ đơn giản là chắc chắn sẽ ăn report DMCA nhé.)
2. Demo duy nhất 2 ví dụ đơn giản và cực kỳ dễ hiểu về độ phức tạp của thuật toán trong lập trình
Mình sẽ bắt đầu với ví dụ cơ bản nhất để các bạn dễ hiểu đó là:
* Ví dụ 1: Cho một mảng dữ liệu (Array) có n phần tử là chữ số, và hãy tìm phần tử lớn nhất trong mảng đó.
-> Cách giải quyết cho bài toán trên là chúng ta sẽ phải chạy vòng lặp trên toàn bộ các phần tử của mảng đó để tìm ra thằng lớn nhất, lúc này sẽ dẫn đến khái niệm độ phức tạp O(n) – có thể hiểu là chạy qua n phần tử để tìm kiếm giá trị thoả mãn yêu cầu => (đây là một trong nhiều quy tắc cơ bản để xác định độ phức tạp của 1 thuật toán)
* Ví dụ 2 Tuy nhiên cũng với mảng trên, nếu lúc này mình thay đổi yêu cầu bài toán thành: Tìm phần tử đầu tiên trong mảng mà nó phải thoả mãn việc chia hết cho 2.
-> Dựa vào sự thay đổi yêu cầu trên, lúc này chúng ta sẽ có trường hợp không cần phải chạy vòng lặp để duyệt toàn bộ phần tử của mảng nữa. Ví dụ mảng của mình có 5 phần tử như sau: [1, 5, 10, 12, 17]
-> Giả sử các bạn thích chạy hết toàn bộ mảng thì độ phức tạp ở đây là O(5), tuy nhiên nhìn lại một chút thì thấy phần tử ở vị trí thứ 3 có giá trị 10 thoả mãn điều kiện của đề bài, tức là phần tử đầu tiên trong mảng chia hết cho 2 đúng không?
Lúc này chúng ta chỉ cần chạy vòng lặp đến thằng thứ 3 và thấy thoả mãn rồi thì return dừng chương trình lại luôn, không cần quan tâm tới 2 thằng phía sau nữa cho mất công. Và chúng ta sẽ có độ phức tạp trong trường hợp này chỉ còn là O(3) thay vì O(5) như ban đầu. (Dĩ nhiên nếu xui xui quá mà chỉ có một thằng thoả mãn điều kiện mà nó lại nằm ở cuối mảng thì thôi không cần bàn nữa nhé :))) )
Với 2 ví dụ rất cơ bản như mình đã giải thích ở trên thì mình tin là các bạn đã nắm được tổng quan về độ phức tạp của thuật toán là gì rồi nhé, và mình quyết định sẽ không đưa ra thêm ví dụ phức tạp nào khác nữa trong bài này ví dụ như là O(log(n)), O(n!), O(n^2)…vv để tránh việc các bạn phải đau đầu :))), hãy cứ học dần qua các ví dụ thực tế mà mình sẽ hướng dẫn trong chuỗi series này nhé.
Trong thực tế, dữ liệu đầu vào n cũng như yêu cầu xử lý của bài toán sẽ rất nhiều và đa dạng chứ không có đơn giản như vậy, n có thể là một vài tỷ chẳng hạn, và tuỳ vào từng yêu cầu mà chúng ta sẽ phải tuỳ biến sử dụng các kỹ thuật lập trình để tối ưu độ phức tạp của thuật toán về mức thấp nhất có thể, từ đó giảm thiểu thời gian chờ xử lý của một hoặc nhiều tác vụ, giúp cho trải nghiệm người dùng tốt hơn, tiết kiệm được nhiều chi phí triển khai hơn vì server cũng không phải chạy nhiều dẫn đến tiêu tốn nhiều CPU, RAM, hoặc thậm chí là quá tải…vv
Tiếp theo, các bạn có thể bắt đầu cùng mình luyện thuật toán với chuỗi series Xử lý thuật toán với JavaScript trên trang blog chính thức Trungquandev này cũng như kênh YouTube: Trungquandev Official của mình nha!
Cảm ơn các bạn đã dành thời gian đọc bài viết.
Xin chào và hẹn gặp lại các bạn ở những bài viết tiếp theo.
Best Regards – 💻 Trungquandev Official ❤
Tham khảo kiến thức:
https://en.wikipedia.org/wiki/Algorithm
https://en.wikipedia.org/wiki/Time_complexity
“Thanks for awesome knowledges.”
“ From author: trungquandev ”
Khóa học lập trình làm việc thực tế:
KHOÁ HỌC LẬP TRÌNH MERN STACK 100% DỰ ÁN THỰC TẾ và CHẤT LƯỢNG
