Menu Close

[Algorithms] Phân tích độ phức tạp thuật toán

Nhận dạng độ phức tạp tính toán (time complexity) của thuật toán:
– O(1): nếu đoạn code không có vòng lặp, đệ quy (recursion) và gọi các hàm có độ phức tạp khác hằng số
– O(n): nếu đoạn code có chứa một vòng lặp, và trong vòng lặp chỉ gọi các hàm có độ phức tạp O(1)
– O(n^k): nếu đoạn code có chứa các vòng lặp lồng vào nhau
– O(logn): nếu đoạn code có chứa vòng lặp, và biến tăng nhân/chia cho hằng số.
– O(loglogn): nếu đoạn code có chứa vòng lặp, và biến tăng thay đổi bởi bằng phép lũy thừa.

   for (int i = 2; i <=n; i = pow(i, c)) { 
       // some O(1) expressions
   }

i sẽ nhận lần lượt các hệ số: 2, 2^c, 2^(c^2),…,2^(c^k) và i <= n nên 2^(c^k)<=n –> k <= logc(logn) –> O(loglogn)
Next Post: Tính độ phức tạp của các thuật toán đệ quy (update later)

Leave a Reply

Your email address will not be published. Required fields are marked *