Định nghĩa đơn giản: thì đó là tổng “thời gian” cần thiết để một thuật toán có thể thực thi xong.
Hư cấu à ? Bố run cùng 1 đoạn code trên con server mạnh nhất vịnh Bắc Bộ thì tất yếu là ăn đứt con Celeron của mày rồi còn gì, cần gì phải đo đạt nữa. → Thế nên “ thời hạn ” ở định nghĩa trên chỉ là giá trị ước đạt, và từ những giá trị ước đạt đó để lựa chọn ra một giải pháp tối ưu nhất vận dụng vào trong thực tiễn .Các phương pháp tính TMCác chiêu thức tính TMTM thường được tính bởi các giải pháp sau :Big Oh (O): Code mà chưa cúng, rơi vào case tệ nhất, có thời gian thực thi lâu nhất (Mấy anh dev thích cái lâu lâu này nhất…vì nó thường hay sử dụng nhất thôi)Big Omega (Ω) : Rút kinh nghiệm, cúng ông địa vài kí tỏi rồi, nên rơi vào case tốt nhất, có thời gian thực thi nhanh nhấtBig Theta (Θ) : Bao gồm cả trường hợp tệ nhất và xịn nhất: Code mà chưa cúng, rơi vào case tệ nhất, có thời hạn thực thi lâu nhất ( Mấy anh dev thích cái lâu lâu này nhất … vì nó thường hay sử dụng nhất thôi ) : Rút kinh nghiệm tay nghề, cúng ông địa vài kí tỏi rồi, nên rơi vào case tốt nhất, có thời hạn thực thi nhanh nhất : Bao gồm cả trường hợp tệ nhất và xịn nhất
Trong phạm vi bài viết này mình chỉ nói về Big Oh (O), cái mà mấy đứa “con nhà người ta” nhìn vô 1 đoạn code và phán, “cái này O(n) nè”, “làm zầy O(logn) nhanh hơn nè” và bạn đứng đó nhìn mà éo biết tụi nó nói cái gì!!!
Bắt đầu nhé, ví dụ, bạn ra phố đi bộ Nguyễn Huệ tìm gấu vì bạn đang ế chảy thây ra. Vậy tìm bằng cách nào đây :
Giả sử (n) là tổng số người mà bạn sẽ tương tác ở phố đi bộ
O(n): nếu bạn đi hỏi từng người “Tui đang rảnh, bạn yêu tui cho tui bớt rảnh lại chút được hơm?”, đến khi tìm thấy ai đó say Yes → xongNghĩa là: Nếu số nhọ thì bạn phải hỏi hết (n) người thì có thể tìm được gấu (hoặc cũng có thể không tìm được luôn)O(logn): nếu bạn nói “Ai có khả năng rảnh để yêu tui thì đứng lại đây, còn không thì lui xuống hậu cung dùm”, vậy là đã giảm đi phân nửa thành phần phản động (và cũng có khả năng giải quyết luôn bài toán vì không còn ai ở lại =)) ). Với những người còn lại, tiếp tục hỏi câu hỏi trên…đến khi không còn 1 ai… à, đến khi tìm được người cuối cùng chịu làm gấu của bạn → xongNghĩa là: cứ mỗi lần bạn đặt câu hỏi thì sẽ giảm đc 1/2 số lượng người. Nếu n = 10 thì xui lắm hỏi 5 lần là xongO(n²): nếu bạn túm 1 người đi đường A và hỏi “Thím, yêu tui nha?”, nếu A nói không, 2 người ngồi xuống đàm đạo, bạn hỏi ý kiến của A về (n-1) người còn lại, xem họ có yêu bạn không… và bạn cứ đi hỏi rồi ngồi đàm đạo… đến khi xuống lỗ thì thôi → xongNghĩa là: cứ gặp 1 người bạn phải hỏi (n) lần (1 lần hỏi người đó, và n-1 lần hỏi người đó những người còn lại)nếu bạn đi hỏi từng người “ Tui đang rảnh, bạn yêu tui cho tui bớt rảnh lại chút được hơm ? ”, đến khi tìm thấy ai đó say Yes → xongNghĩa là : Nếu số nhọ thì bạn phải hỏi hết ( n ) người thì hoàn toàn có thể tìm được gấu ( hoặc cũng hoàn toàn có thể không tìm được luôn ) : nếu bạn nói “ Ai có năng lực rảnh để yêu tui thì đứng lại đây, còn không thì lui xuống hậu cung dùm ”, vậy là đã giảm đi phân nửa thành phần phản động ( và cũng có năng lực xử lý luôn bài toán vì không còn ai ở lại =)) ). Với những người còn lại, liên tục hỏi thắc mắc trên … đến khi không còn 1 ai … à, đến khi tìm được người ở đầu cuối chịu làm gấu của bạn → xongNghĩa là : cứ mỗi lần bạn đặt câu hỏi thì sẽ giảm đc 1/2 số lượng người. Nếu n = 10 thì xui lắm hỏi 5 lần là xong : nếu bạn túm 1 người đi đường A và hỏi “ Thím, yêu tui nha ? ”, nếu A nói không, 2 người ngồi xuống đàm đạo, bạn hỏi quan điểm của A về ( n-1 ) người còn lại, xem họ có yêu bạn không … và bạn cứ đi hỏi rồi ngồi đàm đạo … đến khi xuống lỗ thì thôi → xongNghĩa là : cứ gặp 1 người bạn phải hỏi ( n ) lần ( 1 lần hỏi người đó, và n-1 lần hỏi người đó những người còn lại )
Vậy đó, đó chính là độ phức tạp của thuật toán, đơn giản phải không.
Xem thêm: merit tiếng Anh là gì?
Xem thêm : Nhà Thầu Liên Danh Là Gì – Nhà Thầu Liên Danh Hay Liên Doanh
Các quy tắc tính TMCác quy tắc tính TM
Ở trên chỉ là ví dụ để các bạn hiểu rằng cùng một bài toán nhưng có rất nhiều cách giải quyết, và mỗi cách sẽ có 1 độ khó (phức tạp) tương ứng. Vậy rồi sao? Cái đó ai chẳng biết, vấn đề là mấy cái O…O… gì đó làm sao tính được.
Cái gì cũng sẽ có quy tắc của nó, để tính TM thì tất cả chúng ta thường vận dụng 4 quy tắc sau :Quy tắc bỏ hằng số: VD: bạn tính ra TM của một function là 2n + 3n² + 10000 thì bỏ hết những hằng số (mấy số nằm dưới): 2, 3, 10000 → và nó trở thành n + n²Ủa sao kì vậy? Mấy số đó cũng ảnh hưởng tới tốc độ thực thi function mà? → Đơn giản là vì nó không đáng kể. Bạn xin vợ 50k (n) đi nhậu thì bạn thích vợ cho 2 * 50k hay 500k? → giá trị n lớn thì có giá trị hơn là hằng số → vứtQuy tắc lấy Max:Cũng VD trên sau khi đã ra n + n² bạn tiếp tục lấy Max của phép toán → nó thành n²Đậu xanh tao có mấy chục đi nhậu mà mày kiếm chuyện bòn rút hết của tao vậy? → tại vì 500k cũng không là gì so với 500k² =)) → vứtQuy tắc cộng:Cũng VD trên sau khi đã xin vợ được n², bạn đi xin tiếp vợ 2 được m³ (cho nhiều hơn hèn chi yêu vợ 2 hơn) → cộng lại đc n² + m³Ủa? Sao giờ mày cộng mà hồi nãy mày lại vứt đám tiền lẻ kia → tại cùng một người thì lấy 1 lần thôi má, tham vừa thôi (m với n khác nhau)Quy tắc nhân:Hôm nay xui sao vợ 2 không cho tiền mà vợ lớn thì chỉ cho có 20k (n). Cầm 20 tờ 1k trong tay chẳng khác nào thằng ăn xin ra đường, không thể đi nhậu, bạn đành lấy nó đi đầu tư vào 20 bàn lô tô với mấy đứa hàng xóm. Cứ 1k thì bạn chơi đc 2 ván (m) → chơi được 40 ván → n * mVí dụVD : bạn tính ra TM của một function làthì bỏ hết những hằng số ( mấy số nằm dưới ) : → và nó trở thànhỦa sao kì vậy ? Mấy số đó cũng ảnh hưởng tác động tới vận tốc thực thi function mà ? → Đơn giản là vì nó không đáng kể. Bạn xin vợ 50 k ( n ) đi nhậu thì bạn thích vợ cho 2 * 50 k hay 500 k ? → giá trị n lớn thì có giá trị hơn là hằng số → vứtCũng VD trên sau khi đã rabạn liên tục lấy Max của phép toán → nó thànhĐậu xanh tao có mấy chục đi nhậu mà mày kiếm chuyện bòn rút hết của tao vậy ? → tại vì 500 k cũng không là gì so với 500 k² =)) → vứtCũng VD trên sau khi đã xin vợ được, bạn đi xin tiếp vợ 2 được ( cho nhiều hơn hèn chi yêu vợ 2 hơn ) → cộng lại đcỦa ? Sao giờ mày cộng mà hồi nãy mày lại vứt đám tiền lẻ kia → tại cùng một người thì lấy 1 lần thôi má, tham vừa thôi ( m với n khác nhau ) Hôm nay xui sao vợ 2 không cho tiền mà vợ lớn thì chỉ cho có 20 k ( n ). Cầm 20 tờ 1 k trong tay chẳng khác nào thằng ăn xin ra đường, không hề đi nhậu, bạn đành lấy nó đi góp vốn đầu tư vào 20 bàn lô tô với mấy đứa hàng xóm. Cứ 1 k thì bạn chơi đc 2 ván ( m ) → chơi được 40 ván → Ví dụSau khi đã biết được các quy tắc trên thì bạn hoàn toàn có thể tự tin tìm được TM của một function chưa ? Nếu vẫn chưa thì thử xem VD đơn cử sau :
Các dòng code 2, 3, 4, 7, 8, 9, 12, 13, 14: đều là các phép gán, print nên TM của mỗi đứa chỉ có 1 (có phức tạp mợ gì đâu) → 9 dòng đó có TM là 9Dòng 5,6 là for lồng trong for: mỗi thằng i sẽ chạy m lần → Áp dụng quy tắc nhân ở trên → n * mDòng 10, 11 cũng là for lồng trong for → x * x → x²Áp dụng quy tắc cộng cho tất cả → 9 + n*m +x²Áp dụng tiếp quy tắc bỏ hằng số → n*m + x²Áp dụng quy tắc Max → max (n*m, x²) → Kết quả cuối cùngCác dòng code 2, 3, 4, 7, 8, 9, 12, 13, 14 : đều là các phép gán, print nên TM của mỗi đứa chỉ có 1 ( có phức tạp mợ gì đâu ) → 9 dòng đó có TM làDòng 5,6 là for lồng trong for : mỗi thằng i sẽ chạy m lần → Áp dụng quy tắc nhân ở trên → Dòng 10, 11 cũng là for lồng trong for → x * x → Áp dụng quy tắc cộng cho tổng thể → Áp dụng tiếp quy tắc bỏ hằng số → Áp dụng quy tắc Max → → Kết quả sau cuối
Ủa mày gạt tao nữa à? Sao có phép tính lũy thừa kìa, max của nó phải là x² chứ? → Chưa chắc đâu pa, vì m, n, x là bao nhiêu làm sao thím biết được, ở vd trên vứt hết giữ lại n² vì cùng là biến n
Vậy chẳng lẽ cứ muốn tìm TM thì phải banh code là để làm tính sao? Cũng không cần thiết lắm vì thế giới đã làm giúp bạn hết rồi. Bạn có thể tìm hiểu thêm về 8 TM thông dụng nhất hoặc TM của các bài toán phổ biến ở đây.
Tóm lạiTóm lạiĐó là cách mà các bạn hoàn toàn có thể tính ra được TM của một bài toán. Từ nay khi nghe ai đó nói thoang thoáng function này có độ phức tạp là O ( n² ) thì bạn hoàn toàn có thể biết được là trong đó sẽ có 2 vòng lặp lồng vào nhau .Nhưng ngoài việc xác lập ( có vẻ như hơi triết lý ) TM như trên thì nó còn ứng dụng gì khác không ? Vì mười ngàn năm nay code của tao vẫn chạy ngon mà. → Đúng rồi, với những bài toán có khoanh vùng phạm vi nhỏ ( n nhỏ ) thì code thế nào cũng được, miễn đúng thì thôi. Nhưng khi tích hợp những bài toán nhỏ ( VD cần sort xong rồi search, vậy dùng thuật toán nào để sort và search ) thì sẽ là một câu truyện khác. Do đó khi biết đc TM của từng bài toán nhỏ, bạn hoàn toàn có thể phối hợp và lựa chọn ra một giải pháp tốt nhất để xử lý yếu tố của mình .
Source: https://final-blade.com
Category: Tiền Điện Tử – Tiền Ảo
