Linear time là gì?

2023-07-30 01:30:04 1757 Lượt xem 92 Lượt thích

Phrase Algorithm

Một thuật toán (algorithm) được cho là có độ phức tạp về thời gian tuyến tính (linear time) khi thời gian chạy thuật toán tăng tuyến tính với độ dài (length) của đầu vào (input).

Đoạn mã trên cho thấy rằng dựa trên độ dài của mảng (n), thời gian chạy sẽ được tăng tuyến tính. Nếu coi thời gian chạy là 1 đơn vị thời gian thì cần n lần 1 đơn vị thời gian để chạy mảng. Do đó, hàm chạy tuyến tính với kích thước đầu vào.