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.
Một số chỉ số độ phức tạp của thuật toán theo mức độ tăng dần
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!)OperationsElements
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