Độ Phức Tạp Của Thuật Toán - Time Complexity - Yêu Lập Trình

Khi lựa chọn thuật toàn để giải quyết một vấn đề cụ thể. Điều đầu tiên các lập trình viên cần chú ý đó là độ phức tạp của thuật toán. Để tính độ phức tạp của thuật toán chúng ta dựa trên hai yếu tố: Độ phức tạp về thời gian chạy thuật toán (số lần thực hiện phép tính) và độ phức tạp về không gian (vùng nhớ lưu trữ). Chúng ta sử dụng ký tự Big-O để phân loại các thuật toán dựa trên thời gian và không gian khi dữ liệu đầu vào tăng lên.

Độ phức tạp của thuât toán coi như một hàm có ký hiệu là Big-O. Với tham số n là kích thước đầu vào, O là kịch bản trong trường hợp tăng trưởng xấu nhất. Hay nói cách khác, Big-O là tính toán thời gian chạy lâu nhất của một thuật toán.

Nội dung của bài

• 1 Một số chỉ số độ phức tạp của thuật toán theo mức độ tăng dần
• 2 Các quy tắc trong tính toán độ phức tạp của thuật toán
  • 2.1 Quy tắc bỏ hằng số
  • 2.2 Quy tắc cộng – lấy giá trị max
  • 2.3 Quy tắc nhân
  • 2.4 Quy tắc tổng quát
• 3 Tổng kết

Một số chỉ số độ phức tạp của thuật toán theo mức độ tăng dần

Big O Notation	Name	Mô tả
O(1)	Constant	Số phép tính là hằng số, không phụ thuộc vào dữ liệu đầu vào. vd: a + b.
O(log n)	Logarithmic	Số phép tính (thời gian thực hiện) tăng theo kích thước dữ liệu theo hàmlogarit. vd: tìm kiếm nhị phân.
O(n)	Linear	Số phép tính phụ thuộc vào dữ liệu đầu vào theo 1 biến. vd: tìm kiếm tuyến tính.
O(n log n)	Linearithmic	Tổng hợp của n và logn (lồng nhau). vd: Heap sort, Merge sort.
O(n2)	Quadratic	Vòng lặp lồng nhau. Ví dụ tìm xem trong tập hợp có phần tử trùng nhau không.
O(n3)	Cubic	Ba vòng lặp lồng nhau. Ví dụ tính bài toán: 3*x + 5*y + 9 * z = 100
O(2n)	Exponential	Thời gian chạy theo cấp số nhân (cơ số 2) có nghĩa là các phép tính được thực hiện bởi một thuật toán sẽ tăng gấp đôi mỗi khi đầu vào tăng lên.
O(n!)	Factorial	Thời gian chạy giai thừa như hoán đổi một chuỗi.

Tôi sẽ bổ sung các ví dụ cụ thể trong thời gan tới.

O(log n), O(1) O(n) O(n log n) O(n^2) O(2^n) O(n!) Operations Elements

Các quy tắc trong tính toán độ phức tạp của thuật toán

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ươngthì có thể coi đoạn chương trình đó có độ phức tạp tính toán là O(f(n)).

Quy tắc cộng – lấy giá trị max

Coi T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình B1 và B2. Trong đó T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của đoạn hai chương trình đó nối tiếp nhau là T(n)=O(max(f(n),g(n)))

Ví dụ:

Lệnh gán x +=15 tốn một hằng thời gian hay O(1), lệnh đọc dữ liệu readln(x) tốn một hằng thời gian hay O(1).Vậy thời gian thực hiện cả hai lệnh trên nối tiếp nhau là O(max(1,1))=O(1)

Quy tắc nhân

Coi T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình B1 và B2 và T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện của đoạn hai đoạn chương trình đó lồng nhau là T(n) = O(f(n).g(n))

Quy tắc tổng quát

• Thời gian thực hiện mỗi lệnh gán là O(1)
• Thời gian thực hiện mệnh đề if…else là thời gian lớn nhất thực hiện khối lệnh trong if hoặc trong else. Thời gian kiểm tra điều kiện là O(1)
• Thời gian thực hiện chuỗi lệnh tuần tự được xác định bằng quy tắc cộng. Tức là thời gian thực hiện một lệnh lâu nhất trong chuỗi lệnh.
• Thời gian thực hiện vòng lặp là tổng số lần thực hiện khối lệnh trong thân vòng lặp. Nếu thời gian thực hiện khối lệnh trong thân vòng lặp không đổi thì thời gian thực hiện vòng lặp là tích của số bước thực hiện vòng lặp và thời gian thực hiện thân vòng lặp.

Ví dụ cài đặt thuật toán nổi bọt bằng ngôn ngữ Python:

def bubble_sort(arr): n = len(arr) # Duyệt qua tất cả các phần tử của mảng for i in range(n): # {1} for j in range(0, n-i-1): # {2} # duyệt qua các phần tử của mảng từ 0 đén n-i-1 # Đổi chỗ nếu tìm thấy phần tử lớn hơn if arr[j] > arr[j+1] : # {3} arr[j], arr[j+1] = arr[j+1], arr[j] # {4}

Ta thấy trong chương trình gồm một lệnh lặp {1}, lồng trong lệnh lặp {1} là lệnh lặp {2}. Lồng trong lệnh lặp 2 là lệnh điều kiện {3}, trong lệnh điều kiện {3} là khối lệnh {4}.Khối lệnh 4 thực ra là ba lệnh:

temp = arr[j+1] arr[j+1] = arr[j] arr[j] = temp

Chúng ta sẽ phân tích từ trong ra ngoài:

Khối 3 lệnh trên tốn thời gian là O(1), câu lệnh điều kiện cũng tốn thời gian là O(1). Do đó thời gian thực hiện lệnh {3} là O(1).

Vòng lặp {2} chạy n-i lần, mỗi lần O(1) nên thời gian chạy vòng lặp 2 là O((n-i) * 1) = O(n-i).

Vòng lặp {1} có i chạy từ 0 đến n-1, từ đó to có thời gian thực hiện vòng lặp {1} hay độ phức tạp của thuật toán là: O(n^2)

Tổng kết

Tính toán độ phức tạp của thuật toán có lẽ hơi khó hiểu với những người mới học lập trình. Tôi sẽ cố gắng bổ sung nhiều ví dụ trực quan hơn trong thời gian tới.

Tham khảo:https://adrianmejia.com/most-popular-algorithms-time-complexity-every-programmer-should-know-free-online-tutorial-course