Time Limit Exceeded Trong Thuật Toán Và Cách Khắc Phục.

Time Limit Exceeded Trong Thuật Toán Và Cách Khắc Phục.

Trong quá trình học lập trình, bạn đã từng nghe qua về thuật ngữ "Time Limit Exceeded" chưa, hay đã có lúc nào bạn chạy một thuật toán mà chờ mãi  vẫn không có kết quả trả về. Hôm nay mình sẽ giúp các bạn hiểu và khắc phục lỗi này nhé

1. Time Limit Exceeded là gì?

Time limit exceeded (TLE) có nghĩa là chạy quá giới hạn thời gian cho phép. Vậy tạo sao lại phải có giới hạn thời gian của thuật toán, đó là vì máy tính chỉ thực hiện được một lượng phép tính trong thời gian nhất định, nếu code của bạn yêu cầu máy tính phải thực hiện một số lệnh quá lớn thì máy tính sẽ chạy rất lâu hoặc có thể chạy không bao giờ dừng. Để tránh điều đó xảy ra, thì trong các của thi hoặc một số trang web với tính năng chấm bài tự động sẽ phải đưa ra giới hạn thời gian để thực hiện bài toán đó. Nếu khi thuật toán của bạn chạy quá giới hạn ở một test case nào đó, thì hệ thống sẽ xem như bạn đã sai ở test case đó.

2. Tại sao lại xảy ra lỗi Time Limit Exceeded.

2.1 TLE do vòng lặp chạy vô tận.

Trường hợp này thường xảy ra thường khi coder chưa thực sự cẩn thận, họ không lường trước được những trường hợp mà vòng lặp (while, for, ...) không thể kết thúc.

Ví dụ với chương trình sau đây:

#include <iostream>

using namespace std;

int main(){
	int n;
	n = 10;
	while (n > 0){
		cout << "Time Limit Exceeded." << endl;
		n = n + 2;
	}
	
	return 0;
}

Dễ dàng đoán ra được kết quả khi chạy chương trình trên sẽ là:

Đừng chờ nó kết thúc, vì nó sẽ chạy mãi như thế đấy.

Lỗi xảy ra là do các câu lệnh xử lý ở trong vòng lặp không thể làm cho vòng lặp kết thúc.

2.2 Lỗi do không tính được độ phức tạp của thuật toán.

Trong phần này xuất hiện một thuật ngữ quen thuộc là độ phức tạp (ĐPT) của thuật toán, vậy ĐPT của thuật toán là gì, và tính nó như thế nào?

Vấn đề này mình xin phép chỉ nói qua, đủ cho các bạn hiểu và tính được những ĐPT cơ bản.

Gọi n là độ lớn đầu vào. Tùy thuộc từng bài toán mà n có thể nhận những giá trị khác nhau. Chẳng hạn, bài toán tính giai thừa thì n chính là số cần tính giai thừa, ví dụ những bài toán về dãy số thì n chính là số lương phần tử của dãy,..

ĐPT không phải là độ đo chính xác số lượng thao tác máy tính cần làm, mà đặc trưng cho động thái của hệ thống khi kích thước đầu vào tăng lên. Chẳng hạn với thuật toán có ĐPT O(n), nếu kích thước đầu vào tăng gấp đôi thì có thể ước tính rằng các thao tác cần dùng cũng tăng khoảng gấp đôi. Nhưng với thuật toán có ĐPT bình phương O(n2) thì thao tác cần dùng sẽ tăng gấp bốn. Mặt khác, với thuật toán có ĐPT hàm mũ O(2n) thì chỉ cần cộng thêm ba đơn vị vào độ lớn đầu vào thì cũng đã làm sô lượng thao tác tăng lên tám lần rồi.

-ĐPT của phép tính.

Tất cả những phép gán, thực hiện phép tính, so sánh, lệnh switch, nhập xuất dữ liệu, return, ... đều có ĐPT là O(1) nghĩa là dù dữ liệu và có như thế nào cũng không ảnh hưởng nhiều đến thời gian thực hiện những câu lệnh đó.

-ĐPT của vòng lặp.

Nhiều bạn mới thường có suy nghĩ là ĐPT của mỗi vòng lặp sẽ là O(n), nhưng điều đó là không đúng. Sau đây mình sẽ giúp các bạn biết thêm về các tính ĐPT của vòng lặp, cách tính này mình áp dụng rất nhiều khi đánh giá thuật toán. (áp dụng cho những vòng lặp thực hiện ít nhất một lần và không phải là vòng lặp vô tận).

Trong  vòng lập thì chúng ta sẽ quan tấm tới ba điều đó là: khởi tạo biến lặp, điều kiện lặp cập nhật biến lặp.

for (khởi tạo giá trị biến lặp; điều kiện lặp; cập nhật biến lặp)
{
    // các lệnh cần lặp
}
	//Khởi tạo biến lặp
	while (Điều kiện lặp){
		// cập nhập biến lặp		
	}

+ Với những vòng lặp mà việc cập nhật biến lặp theo kiểu nhân với một số.
Ví dụ với i là biến lặp mà nếu việc cập nhập biến lặp là i *= k (Với k không thay đổi trong vòng lặp).

Thì ĐPT của vòng lặp đó sẽ là O(logN).

Ví dụ với chương trình sau:

#include <iostream>

using namespace std;

int main(){
	long long n = 999999999999999999;
	
	for (long long i = 1; i < n; i *= 11){
		cout << i << endl;
	}
	
	
	return 0;
}

Cho dù n rất lớn nhưng với ĐPT là O(logN) thì vòng lặp này sẽ chạy rất nhanh:

Kết quả khi chạy chương trình trên:

Với những vòng lặp như thế thì này thì hầu như không thể lỗi TLE.

+ Với những vòng lặp mà việc cập nhật biến lặp theo kiểu cộng với một số.

Ví dụ với i là biến lặp mà nếu việc cập nhập biến lặp là i += k (Với k không thay đổi trong vòng lặp).

Gọi A là giá trị khởi tạo của biến lặp, B là giá trị đầu tiên của biến lặp khi thoát khỏi vòng lặp:

	for (long long i = A; i < B; i += K)

Thì ĐPT của vòng lặp đó sẽ là O(nx). Trong đó x được tính theo công thức sau:

X  = Bậc của (B - A) - Bậc của (k).

Trong đó bậc chính là số mũ cao nhất trong biểu thức đó.

Một số ví dụ:

Với vòng lặp sau:

	for (long long i = 123; i < n; i += 2)

Thì ta tính được X = Bậc của (n - 123) - Bậc của (2) = 1 - 0 = 1.
Như vậy vòng for trên có ĐPT là O(nx) = O(n).

Với vòng lặp sau:

	for (long long i = n; i < n*n; i += n/2)

Thì ta tính được X = Bậc của (n*n - n) - Bậc của (n/2) = 2 - 1 = 1.
Như vậy vòng for trên có ĐPT là O(nx) = O(n).

Với vòng lặp sau:

	for (int i = n - 27; i < n; i++)

Thì ta tính được X = Bậc của (n - (n - 27)) - Bậc của (1) = 1 - 1 = 0.
Như vậy vòng for trên có ĐPT là O(nx) = O(1).

Với vòng lặp sau:

	for (int i = n*n; i < n*n*n; i += n)

Thì ta tính được X = Bậc của (n3 - n2) - Bậc của (n) = 3 - 1 = 2.
Như vậy vòng for trên có ĐPT là O(nx) = O(n2).

Lưu ý:

  • Với những vòng lặp lồng nhau thì ĐPT sẽ bằng tích của các ĐPT của các vòng lặp.
    Ví dụ đoạn code sau sẽ có ĐPT là O(nlogN):
    	for (int i = 1; i < n; i++){
    		for (int j = 1; j < n; j*=2)?{
    			
    		}
    	}​
  • ĐPT của cả thuật toán sẽ là ĐPT lớn nhất của từng thành phần.

3. Cách khắc phục lỗi Time Limit Exceeded.

Thời gian chạy của thuật toán ngoài phụ thuộc vào máy tính của bạn cũng như ngôn ngữ lập trình mà bạn sử dụng, tuy vậy nhưng chúng ta cũng phải:

3.1 Tránh vòng lặp vô tận.

Nên kiểm tra thật kỹ sau khi viết mỗi vòng lặp phải đảm bảo răng vòng lặp luôn được kết thúc, những trường hợp này thường xử lý khá dễ.

3.2 Tìm thuật toán có ĐPT hợp lý.

Một số ĐPT sắp xếp theo thứ tự ưu tiên là: O(1), O(logN), O(căn(n)), O(n), O(P(n)), O(kn), O(n!),...

Điều này các bạn cần phải làm nhiều bài tập sẽ quen dần với cách sử dụng các thuật toán sao cho không TLE. Hầu hết các ngôn ngữ chỉ thực hiện được trong giới hạn 108 thao tac là sẽ không bị TLE. Nến với mỗi bài toán các bạn cần tìm thuật toán tốt nhất để số lượng thao tác không vượt qua 108.

  • Đối với các bài tập về dãy số, với n là sô phần tử trong dãy thì ĐPT bài toán nên chọn là:
    • Với n ≤ 104, nên chọn những thuật toán ĐPT O(n2) hoặc nhỏ hơn.
    • Với n ≤ 108, nên chọn nhữngthuật toán ĐPT O(n) hoặc nhỏ hơn.
  • Với những bào toán xử lý số n:
    • n ≤ 104, nên chọn những thuật toán ĐPT O(n2) hoặc nhỏ hơn.
    • n ≤ 108, nên chọn những thuật toán ĐPT O(n) hoặc nhỏ hơn.
    • n ≤ 109, nên chọn những thuật toán ĐPT O(căn(n)) hoặc nhỏ hơn.
    • n ≤ 1018, nên chọn những thuật toán ĐPT O(logN) hoặc nhỏ hơn.

4. Kết.

Để khắc phục lỗi Time limit exceeded các lập trình viên nên tránh lỗi các vòng lặp vô tận và nên chọn những thuật toán có độ phức tạp phù hợp nhất với bài toán. Trên đây là những kinh nghiệm của mình về cách tránh lỗi TLE, mong mọi người góp ý để bài viêt được phát triển hơn.