Độ Phức Tạp Của Thuật Toán Và Lựa Chọn Cách Giải Thuật

Một số anh em tham gia CodeLearn nhiều khi chạy bài tập bị quá thời gian. Lí do là code của các bạn chạy mất quá nhiều thời gian

Tại sao thời gian lại quan trọng?

• Trong 1 số chương trình, sản phẩm phần mềm nếu xử lí quá chậm sẽ gây khó chịu cho người dùng ứng dụng. Lấy ví dụ bạn mua hàng mà bấm nút tìm kiếm mất 1 phút thì bạn có khó chịu không? Nếu thời gian tìm kiếm của google cho mỗi từ khoá tốn 5 giây thì liệu google có trở thành công cụ tìm kiếm số 1 thế giới hay không?
• Thời gian chạy lâu gây tốn CPU, làm giảm số lượng người dùng mà máy tính/máy chủ có thể phục vụ người dùng (với ứng dụng có máy chủ)

Do đó, các bài tập ở CodeLearn khi đưa ra đều có giới hạn thời gian để người dùng suy nghĩ, lựa chọn giải thuật phù hợp. Đó là thời gian chạy.

Vậy độ phức tạp thuật toán là gì, có liên quan gì tới thời gian chạy?

1. Độ phức tạp thuật toán là gì?

Về lý thuyết, các bạn có thể tìm theo từ khoá algorithm complexity hoặc đọc ở đây 

Nói ngắn gọn thì, mỗi một bài toán có giới hạn/kích thước của đầu vào. Độ phức tạp thuật toán là 1 khái niệm/định nghĩa/định lượng tương đối thể hiện số phép toán của giải thuật so với kích thước của đầu vào.

Ví dụ cho dễ hiểu:

• Một mảng có n phần tử. Hãy tìm phần tử lớn nhất trong mảng
  Bài này tất nhiên chẳng có cách nào khác, bạn sẽ duyệt toàn bộ phần tử trong mảng (duyêt qua mảng n lần) để tìm ra phần tử lớn nhất. Độ phức tạp thuật toán ở đây có thể hiểu là O(n) (chạy qua n phần tử để tìm kiếm)
• Một mảng có n phần tử. Hãy sắp xếp mảng theo thứ tự tăng dần
  Bài này quá quen nhỉ. Bạn thường dùng 2 vòng lặp từ i->n và từ j->n để đổi chỗ. Lúc này độ phức tạp thuật toán là O(n^2)
  Tuy nhiên với 1 số giải thuật sắp xếp như quicksort, độ phức tạp chỉ là O(n*log(n)). 
  Bạn thử thay n=10, thì giải thuật bên trên có thể hiểu sẽ chạy xấp xỉ là 10*10=100 phép tính, nhưng giải thuật Quicksort thì chỉ dùng khoảng 10 phép tính. Với n rất nhỏ, 100 hay 1000 thì chương trình đều chạy có thời gian xấp xỉ bằng nhau. Thật ra kết quả là có chênh, nhưng quá nhỏ nên các bạn không thấy. Nhưng với n cực lớn, ví dụ 100000 phần tử, thì thuật toán có độ phức tạp O(n^2) với O(nlogn) là cực kì khác biệt.
• Cho một mảng có n phần tử đã sắp xếp. Hãy tìm xem có phần tử x hay không?
  Bài này nếu các bạn duyệt từ 1 tới n để tìm xem có x hay không, độ phức tạp vẫn là O(n)
  Tuy nhiên nếu để ý, do mảng này là mảng đã sắp xếp, nên bạn có thể áp dụng thuật toán tìm kiếm nhị phân. Tức là bạn chặt dãy ra làm 2, xem X lớn hay nhỏ hơn phần tử ở giữa, nếu nhỏ hơn thì tìm kiếm ở đoạn dưới, nếu lớn hơn thì tìm kiếm ở đoạn trên. Cứ như vậy bạn chặt dãy ra làm 2 liên tục, thì số phép tìm kiếm sẽ là log2 của n, sẽ nhanh hơn nhiều lần so với giải thuật tìm kiếm tuần tự bên trên.
  
  Nếu không tin, hãy thử code và đo thời gian với số n cực lớn nhé.

Và như bạn thấy đó, máy tính của chúng ta có tốc độ là khác nhau. Có thể hiểu là, cùng có 100000 phép tính, thì máy của ông A có thể chạy nhanh hơn máy ông B. Do đó, độ phức tạp giải thuật có thể thể hiện tương đối chính xác thuật toán nào nhanh hay chậm, so với việc đo thời gian chạy trên các máy khác nhau. Có nhiều bạn cũng comment tại sao chạy ở máy ở nhà thì không quá thời gian, lên server thì bị quá. Cũng là cùng lí do như thế.

2. Chọn giải thuật phù hợp

Như giải thích ở trên, độ phức tạp thuật toán có thể hiểu là số phép toán thực hiện của một hàm dựa trên kích thước tối đa của dữ liệu. Độ phức tạp thuật toán (trên cùng 1 máy) có thể hiểu là nó tỉ lệ thuận (1 cách tương đối) với thời gian chạy.
Mình xem nhiều bài tập của các bạn thấy các bạn chọn giải thuật không phù hợp dẫn đến thời gian chạy cực lâu. Mình ví dụ nha:

• Tính tổng các số nguyên từ 1 -> n
  Bài này ai dùng công thức thì 1 dòng là ra: n*(n+1)/2. Giải thuật này có độ phức tạp là O(1) (1 phép toán)
  Với các bạn dùng vòng lặp từ 1 -> n để tính tổng, độ phức tạp là O(n). Với n bằng 1 tỷ, tương đương bạn thực hiện 1 tỷ lần phép toán cộng
  Bạn hiểu thời gian chạy chênh lêch lớn như thế nào rồi chứ?
• Bài toán kiểm tra số nguyên tố
  Bài này cũng đơn giản thôi. Nhưng nhiều bạn cũng chọn giải thuật phức tạp
  Các bạn chạy để kiểm tra từ 1->n, độ phức tạp là O(n). Các bạn chạy từ 1->sqrt(n) (căn bậc 2 của n) thì đã giảm rất nhiều phép toán, nếu bạn nào còn tăng bước nhảy lên bằng 2 (kiểm tra có chia hết cho 2,3, 5, 7, 9, 11, ... thay vì 2,3,4,5,6, ....) thì số phép toán lại giảm thêm nữa.
  Do đó, ngay từ bài số nguyên tố, việc sử dụng vòng lặp để kiểm tra các bạn đã có thể tối ưu cực nhiều. Bạn có thể thử bài này với số n cực lớn và gọi đi gọi lại nhiều lần để đo độ chênh lệch thời gian nha.
• Bài toán tính tổng các số nguyên tố nhỏ hơn hay bằng n
  Bài này cũng giống bài trên. Độ phức tạp giải thuật của việc kiểm tra số nguyên tố giả sử đang là O(n)
  Nếu với mỗi 1 số từ 1 tới n, bạn lặp lại việc kiểm tra 1 cách thông thường, độ phức tạp thuật toán của giải thuật này là O(n^2)
  Bài này nếu cho n=1000000, đa phần sẽ ko chạy được. Do số phép toán cực nhiều.
  Đối với bài này, nếu bạn dùng sàng nguyên tố (ý tưởng là loại bỏ các hợp số), thì độ phức tạp thuật toán xấp xỉ O(nlogn). Chi tiết tham khảo ở đây nhé.

3. Tổng kết

Hiểu rõ về khái niệm độ phức tạp thuật toán và cách tính toán độ phức tạp của giải thuật (của mình hay của người khác) bạn sẽ tối ưu thuật toán để đáp ứng thời gian chạy tốt hơn ví dụ như làm ứng dụng của bạn chạy nhanh, thời gian phản hồi cao, ... Do đó, với mỗi bài toán hay yêu cầu cụ thể, hãy xem xét độ lớn của tập dữ liệu mà chọn giải thuật cho phù hợp. Chúc anh em thành công

Bài viết theo ý hiểu của mình, cố gắng đơn giản hoá cho anh em, có gì anh em mạnh dạn góp ý nha.