Độ phức tạp thời gian

Chạy một chương trình cần có thời gian. Biết trước chương trình mất bao lâu cũng rất hữu ích khi tạo các chương trình hiệu quả. Trong lập trình, thời gian cần thiết để chạy một chương trình được gọi là độ phức tạp thời gian (time complexity).

 Ví dụ:

for(int i=0;i<5;i++{
   cout<<i<<endl;
}

Trong ví dụ trên, vòng lặp lặp lại năm lần, vì vậy độ phức tạp thời gian là 5. Nói ngắn gọn, độ phức tạp thời gian cho biết số lần lặp mà chương trình thực hiện. Nếu chương trình lặp lại một lần thì độ phức tạp là một, nhưng nếu chương trình lặp lại một số lần tùy ý n thì độ phức tạp thời gian là n.

Độ phức tạp thời gian dùng ký hiệu big O để biểu thị độ phức tạp, và ta không bao giờ viết các giá trị hằng số bên trong ký hiệu này. Ví dụ, năm lần lặp hoặc sáu lần lặp đều được biểu thị là O(1), còn N lần lặp hoặc 2N lần lặp được biểu thị là O(N). Khi phân tích độ phức tạp thời gian của một chương trình, ta xét trường hợp xấu nhất và tính số lần lặp mà chương trình có thể chạy.

Trong khóa học này, bạn cần hiểu tầm quan trọng của độ phức tạp thời gian và một số dạng của nó. Chúng ta sẽ thảo luận về chủ đề này trong bài học tiếp theo.

Đọc bài viết dưới đây để tìm hiểu thêm về phân tích độ phức tạp thời gian.

Độ phức tạp thời gian