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?
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:
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ợpNhư 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.
3. Tổng kếtHiể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. Giới thiệu về cuốn sách này Page 2Giới thiệu về cuốn sách này
 Thông thường khi tính toán độ phức tạp của một thuật giải thì thời gian thực hiện là khía cạnh quan trọng của một giải thuật. Việc chọn một giải thuật đưa đến kết quả nhanh nhất là một đòi hỏi thực tế. Thời gian thực hiện giải thuật bằng chương trình máy tính phụ thuộc vào rất nhiều yếu tố. Bài viết này sẽ giúp các bạn biết một số khái niệm các các phân tích, đánh giá độ phức tạp của một thuật toán. 1. Giới thiệu (Introduction) – Như chúng ta được biết thì thời gian thực hiện của giải thuật phụ thuộc vào rất nhiều yếu tố. Trong đó yếu tố cần chú ý nhất là kích thước của dữ liệu đưa vào. Dữ liệu càng lớn thì thời gian xử lý càng chậm. Chẳng hạn như thời gian sắp xếp một dãy số phải chịu ảnh hưởng của các số thuộc dãy số đó. Nếu gọi n là kích thước dữ liệu đưa vào thì thời gian thực hiện của giải thuật có thể biểu diễn một cách tương đối như một hàm của n: T(n). – Phần cứng máy – Nếu thời gian thực hiện một giải thuật là T1(n) = n2 và thời gian thực hiện của một giải thuật khác là T2(n) = 100n thì khi n đủ lớn thời gian thực hiện của giải thuật T2 rõ ràng nhanh hơn T1. Khi đó, nếu nói rằng thời gian thực hiện giải thật tỉ lệ thuận với n hay tỉ lệ thuận với n2 cũng cho ta một cách đánh giá tương đối về tốc độ thực hiện của giải thuật đó khi n khá lớn. – Cách đánh giá thời gian thực hiện của giải thuật độc lập với máy tính và các yếu tố liên quan tới máy tính như vậy sẽ dẫn tới khái niệm gọi là độ phức tạp của giải thuật. 2. Các ký pháp để đánh giá độ phức tạp tính toán. Cho một giải thuật thực hiện trên dữ liệu với kích thước n. Giả sử T(n) là thời gian thực hiện một giải thuật đó, g(n) là một hàm xác định dương với mọi n. Khi đó ta nói độ phức tạp tính toán của giải thuật là: – O(g(n)) nếu tồn tại các hằng số dương c và n0 sao cho T(n) ≤ c.g(n) với mọi n ≥ n0 . Ký pháp này được gọi là ký pháp chữ O lớn (big-oh notation). Trong ký pháp chữ O lớn, hàm g(.) được gọi là giới hạn trên (asymptotic upper bound) của hàm T(.). – Ω(g(n)) nếu tồn tại các hằng số dương c và n0 sao cho c.g(n) ≤ T(n) với mọi n ≥ n0. Ký hiệu này gọi là ký pháp Ω lớn (big-omega notation). Trong ký pháp Ω lớn, hàm g(.) được gọi là giới hạn dưới (asymptotically lower bound) của hàm T(.). – Θ(g(n) nếu tồn tại các hằng số dương c1, c2 và n0 sao cho c1.g(n) ≤ f(n) ≤ c2.g(n) với mọi n ≥ n0 . Ký pháp này được gọi là ký pháp Θ lớn (big-theta notation). Trong ký pháp Θ lớn, hàm g(.) được gọi là giới hạn chặt (asymptotically tight bound) của hàm T(.).
– Ta nói độ phức tạp tính toán của giải thuật là:
– Ví dụ: Nếu T(n) = n2 + 1, thì:
– Lưu ý rằng không có ký pháp θ nhỏ. Một vài tính chất – Tính bắt cầu (transitivity): Tất cả các ký pháp nêu trên đều có tính bắt cầu.
– Tính phản xạ (reflectivity): Các ký pháp “lớn” mới có tính phản xạ.
– Tính đối xứng (symmetry): chỉ có ký pháp Θ mới có tính đối xứng.
– Tính chuyển vị đối xứng (transpose symmetry):
Để dễ nhớ ta coi các ký pháp Ο, Ω, Θ, ο, ω lần lượt tương ứng với các phép so sánh ≤, ≥, =, <, >. Từ đó suy ra các tính chất trên. 3. Xác định độ phức tạp tính toán của giải thuật Việc xác định độ phức tạp tính toán của một giải thuật bất kỳ có thể rất phức tạp. Tuy nhiên, độ phức tạp tính toán của một số giải thuật trong thực tế có thể tính bằng một số quy tắc đơn 3.1 Quy tắc bỏ hằng số Nếu đoạn chương trình P có thời gian thực hiện T(n) = O(c1.f(n)) với c1 là một hằng số dương thì có thể coi đoạn chương trình đó có độ phức tạp tính toán là O(f(n)). – Chứng minh: T(n) = O(c1.f(n)) nên ∃ c0 > 0 và ∃ n0 > 0 để T(n) ≤ c0.c1 .f(n) với ∀n ≥ n0 . Đặt C = c0.c1 và dùng định nghĩa, ta có T(n) = O(f(n)). Qui tắc này cũng đúng với các ký pháp Ω, Θ, ο và ω. 3.2 Quy tắc lấy MAX Nếu đoạn chương trình P có thời gian thực hiện T(n) = O(f(n) + g(n)) thì có thể coi đoạn chương trình đó có độ phức tạp tính toán O(max ( f(n) , g(n) )). Chứng minh: T(n) = O(f(n) + g(n)) nên ∃C > 0 và ∃ n0 > 0 để T(n) ≤ C.f(n) + C.g(n), ∀n ≥ n0 . Vậy T(n) ≤ C.f(n) + C.g(n) ≤ 2C.max(f(n), g(n)) (∀n ≥ n0 ). Từ định nghĩa suy ra T(n) = O(max( f(n), g(n) )). Qui tắc này cũng đúng với các ký pháp Ω, Θ, ο và ω. 3.3 Quy tắc cộng Nếu đoạn chương trình P1 có thời gian thực hiện T1(n) = O(f(n)) và đoạn chương trình P2 có thời gian thực hiện là T2(n) = O( g(n)) thì thời gian thực hiện P1 rồi đến P2 tiếp theo sẽ là: T1(n) + T2(n) = O(f(n) + g(n)) Chứng minh:
Chọn n0 = max(n1, n2) và c = max(c1, c2) ta có: Với ∀ n ≥ n0 :
Vậy T1(n) + T2(n) = O(f(n) + g(n)). – Quy tắc cộng cũng đúng với các ký pháp Ω, Θ, ο và ω. 3.4 Quy tắc nhân Nếu đoạn chương trình P có thời gian thực hiện là T(n) = O( f(n)). Khi đó, nếu thực hiện k(n) lần đoạn chương trình P với k(n) = O( g(n)) thì độ phức tạp tính toán sẽ là O( g(n). f(n)) Chứng minh Thời gian thực hiện k(n) lần đoạn chương trình P sẽ là k(n)T(n). Theo định nghĩa.
Vậy với ∀ n ≥ max(nT , nk ) ta có k(n).T(n) ≤ cT.ck(g(n).f(n)) – Quy tắc nhân cũng đúng với các ký pháp Ω, Θ, ο và ω. 3.5 Định lý Master (Master Theorem) Cho a ≥ 1 và b >1 là hai hằng số, f(n) là một hàm với đối số n, T(n) là một hàm xác định trên tập các số tự nhiên được định nghĩa như sau: T(n) = a.T(n/b) + f(n) Ở đây n/b có thể hiểu là ⎣n/b⎦ hay ⎡n/b⎤. Khi đó: – Định lý Master là một định lý quan trọng việc phân tích độ phức tạp tính toán của các giải thuật lặp hay đệ quy. Tuy nhiên việc chứng minh định lý khá dài dòng nằm ngoài phạm vi bài viết này. 3.6 Một số tính chất – Ta quan tâm chủ yếu đến các ký pháp “lớn”. Rõ ràng ký pháp Θ là “chặt” hơn ký pháp O và Ω theo nghĩa: nếu độ phức tạp tính toán của giải thuật có thể viết là Θ( f(n)) thì cũng có thể viết là O( f(n)) cũng như Ω( f(n)). Dưới đây là một số cách biểu diễn độ phức tạp tính toán qua ký pháp Θ.
– Dưới đây là một số hàm số hay dùng để ký hiệu độ phức tạp tính toán và bảng giá trị chúng để tiện theo dõi sự tăng của hàm theo đối số n. – Ví dụ: Thuật toán tính tổng các số từ 1 đến n. + Nếu viết theo sơ đồ sau: Đoạn chương trình ở các dòng 1, 2 và 4 có độ phức tạp tính toán là Θ(1). Vòng lặp ở dòng 3 lặp n lần phép gán S := S + i , nên thời gian tính toán tỉ lệ thuận với n. Tức là độ phức tạp tính toán là Θ(n). Dùng quy tắc cộng và quy tắc lấy max ta suy ra độ phức tạp tính toán của giải thuật trên là Θ(n). + Còn nếu viết theo sơ đồ sau: Độ phức tạp tính toán trong trường hợp này là Θ(1), thời gian tính toán không phụ thuộc vào n. 3.7 Phép toán tích cực – Dựa vào những nhận xét đã nêu ở trên về các quy tắc khi đánh giá thời gian thực hiện giải thuật, ta chú ý đặc biệt đến một phép toán mà ta gọi là phép toán tích cực trong một đoạn chương trình. Đó là một phép toán trong một đoạn chương trình mà số lần thực hiện không ít hơn các phép toán khác. – Xét 2 đoạn chương trình tính ex bằng công thức gần đúng: 4. Độ phức tạp tính toán với tình trạng dữ liệu vào Có nhiều trường hợp, thời gian thực hiện giải thuật không phải chỉ phụ thuộc vào kích thước dữ liệu mà còn phụ thuộc vào tình trạng của dữ liệu đó nữa. Chẳng hạn thời gian sắp xếp một dãy số theo thứ tự tăng dần mà dãy đưa vào chưa có thứ tự sẽ khác với thời gian sắp xếp một dãy số đã sắp xếp rồi hoặc đã sắp xếp theo thứ tự ngược lại. Lúc này, khi phân tích thời gian thực hiện giải thuật ta sẽ xét trường hợp tốt nhất, trường hợp trung bình và trường hợp xấu nhất. – Phân tích thời gian thực hiện giải thuật trong trường hợp xấu nhất (worst-case analysis): với một kích thước dữ liệu n, tìm T(n) là thời gian lớn nhất khi thực hiện giải thuật trên mọi bộ dữ liệu kích thước n và phân tích thời gian thực hiện giải thuật dựa trên hàm T(n). – Phân tích thời gian thực hiện giải thuật trong trường hợp tốt nhất (best-case analysis): với một kích thước dữ liệu n, tìm T(n) là thời gian ít nhất khi thực hiện giải thuật trên mọi bộ dữ liệu kích thước n và phân tích thời gian thực hiện dựa trên hàm T(n). – Phân tích thời gian trung bình thực hiện giải thuật (average-case analysis): giả sử rằng dữ liệu vào tuân theo một phân phối xác suất nào đó (chẳng hạn phân bố đều nghĩa là khả năng chọn mỗi bộ dữ liệu vào là như nhau) và tính toán giá trị kỳ vọng (trung bình) của thời gian chạy cho mỗi kích thước dữ liệu n (T(n)), sau đó phân tích thời gian thực hiện giải thuật dựa trên hàm T(n). Khi khó khăn trong việc độ phức tạp tính toán trung bình (bởi việc xác định T(n) trung bình thường phải dùng tới những công cụ tính toán phức tạp), người ta thường chỉ đánh giá độ phức tạp tính toán trong trường hợp xấu nhất. Không nên lẫn lộn các cách phân tích trong trường hợp xấu nhất, trung bình, và giá tốt nhất với các ký pháp biểu diễn độ phức tạp tính toán, đây là 2 khái niệm hoàn toàn phần biệt. Trên phương diện lý thuyết, đánh giá bằng ký pháp Θ(.) là tốt nhất, tuy vậy việc đánh giá bằng ký pháp Θ(.) đòi hỏi phải đánh giá bằng cả ký pháp O(.) lẫn Ω(.). Dẫn tới việc phân tích thuật toán khá phức tạp, gần như phải biểu diễn chính xác thời gian thực hiện giải thuật qua các hàm giải tích. Vì vậy trong những thuật toán người ta thường dùng ký pháp T(n) = O( f(n)). 5. Chi phí thực hiện thuật toán. – Khái niệm độ phức tạp thuật toán đặt ra không chỉ dùng để đánh giá chi phí thực hiện một giải thuật về mặt thời gian mà là để đánh giá chi phí thực hiện giải thuật nói chung, bao gồm cả chi phí về thời gian ( lượng bộ nhớ cần sử dụng). – Thông thường:
+ Để nhấn mạnh tính “tốt” của một giải thuật, các ký pháp O, o thường được sử dụng. Nếu đánh giá được qua O thì không cần đánh giá qua o. Ý nói: chi phí thực hiện thuật toán tối đa là …, ít hơn…. + Đề cập đến tính toán “tồi” của một giải thuật, các ký pháp Ω, ω thường được sử dụng. Nếu đánh giá được qua Ω thì không cần đánh giá qua ω. Ý nói chi phí thực hiện thuật toán tối thiểu là…, cao hơn… (Theo A.K.A DSAP Textbox) |
