Đánh giá thời giá thời gian chạy chương trình

#1

Anh/ chị có thể hướng dẫn em cách đánh gia thời gian chạy chương trình được không ạ?

#2

Chương I Tài liệu chuyên Tin THPT nhé.

Nói thế thôi, bạn cứ nhớ đơn giản là thế này:
Muốn đánh giá đc thời gian chạy chương trình, đầu tiên đánh giá độ phức tạp của code.

  • 1 câu lệnh if…else/phép toán cộng trừ nhân chia/(hình như có cả dịch bit nữa) có độ phức tạp O(1),
  • 1 vòng lặp for/while có độ phức tạp O(n)
    -> có m vòng lặp for/while lồng nhau sẽ có độ phức tạp là O(n^k)
  • Các thuật toán khác nhau sẽ có độ phức tạp khác nhau: chặt nhị phân O(log n), quicksort O(n log n) (log là hàm logarit nepe nhé),… nói chung là gg.

Còn thời gian chạy chương trình thì tuỳ thuộc vào bộ nhớ cần sử dụng và cấu hình máy của bạn. Máy tính sẽ chạy khoảng 10^8 phép tính 1s (khoảng thôi, vì nhiều máy khủng hơn sẽ cho thời gian chạy ít hơn)

#3

Kích hoạt một bộ đếm thời gian ở đầu chương trình. Đến cuối chương trình đọc thời gian đã trôi qua từ bộ đếm ta sẽ thu được thời gian thực hiện chương trình tính bằng tick hoặc ms.
Trong .NET nó là Stopwatch, trong C++ QT nó là QElapsedTimer còn các ngôn ngữ khác thì không rõ.

3 Likes
#4

B thử tìm cái này xem Profiling

#5

Em thắc mắc là cái vòng while em không biết độ phức tập của nó như thế nào, tại while chưa chắc là 0(n^k) ạ!

#6

Mình thấy thực nghiệm là chắc ăn nhất :slight_smile: với bộ test phù hợp để máy chạy vài giây. Ngoài time thì bạn còn phải lưu ý đến mem nữa.

Còn while 2 vòng vẫn có thể là O(n), như một bài trong hình họa (?) máy tính.

2 Likes
#7

while thì tuỳ trường hợp. Có thể nó chạy 3, 4 lần rồi thoát, nhưng có trường hợp chạy mãi không ngừng.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?