Ở bài học này, chúng ta sẽ cùng nhau tìm hiểu một vấn đề sẽ theo chúng ta xuyên suốt khoá học này – độ phức tạp thời gian BigO. Đây là thứ sẽ cho chúng ta biết một thuật toán hoặc cấu trúc dữ liệu thực thi nhanh hay chậm.
Nội dung
Để có thể hiểu được bài học này một cách tốt nhất, các bạn nên có kiến thức cơ bản về các phần:
- Biến, kiểu dữ liệu, toán tử trong C++
- Câu điều kiện, vòng lặp, hàm trong C++
- Tìm hiểu
- Các kiến thức cần thiết để theo dõi khóa học
Trong bài học này chúng ta sẽ tìm hiểu về:
- Khái niệm thời gian chạy của chương trình
- Khái niệm về độ phức tạp thời gian
- Cách đánh giá độ phức tạp của thuật toán
Khái niệm thời gian chạy của chương trình
Thời gian chạy của chương trìnhlà quãng thời gian mà máy tính cần để thực hiện toàn bộ những yêu cầu mà người dùng đặt ra.
Cùng tham khảo ví dụ sau:
`
include
using namespace std; int main[]{ for [int i = 0 ; i < 100 ; ++i]{ cout n; for[int i = 0 ; i < n ; ++i]{ cout n >> m; for[int i = 0 ; i < n ; ++i]{ for[int j = 0 ; j < m ; ++j]{ cout n >> m; for[int i = 0 ; i < n ; ++i]{ cout