a) \(T_1=1+\dfrac{n}{3}=1+\dfrac{1000000}{3}\) (đơn vị thời gian).
b) \(T_2=1+1+\dfrac{n}{3}=2+\dfrac{1000000}{3}\) (đơn vị thời gian).
a) \(T_1=1+\dfrac{n}{3}=1+\dfrac{1000000}{3}\) (đơn vị thời gian).
b) \(T_2=1+1+\dfrac{n}{3}=2+\dfrac{1000000}{3}\) (đơn vị thời gian).
Quan sát và ước lượng thời gian thực hiện các đoạn chương trình 1 và 2 trong Hình 24.2. Chương trình nào chạy nhanh hơn? Vì sao?
Quan sát và thực hiện đánh giá thời gian chạy của các chương trình 1 và 2 trong Hình 24.2. Từ đó biết và hiểu được cách đánh giá thời gian thực hiện chương trình.
Em hãy thiết lập chương trình và tính thời gian chạy thực tế trên máy tính của các chương trình 1 và 2 ở Hình 24.2 với các giá trị n khác nhau từ đó thấy được ý nghĩa sự khác biệt độ phức tạp thời gian của hai chương trình này.
Xác định độ phức tạp thời gian tính toán cho chương trình sau:
n = 1000
sum = 0
i = 1while i <n;
i = i*2
sum = sum + 1
print (sum)
Xác định độ phức tạp thời gian cho chương trình sau:
n = 1000
s = 0
for i in range (n);
s = s + i*(i+1)
print (s)
Đọc, quan sát, thảo luận để biết một số quy tắc đơn giản tính độ phức tạp thời gian thuật toán.
Xác định độ phức tạp thời gian của thuật toán sắp xếp chọn đã được học trong bài 21.
Áp dụng các quy tác trên để tính độ phức tạp của các hàm thời gian sau:
a) T(n) = n3 + nlogn + 2n + 1.
b) T(n) = 3n4 + 2n2logn + 10.
Tính độ phức tạp của các hàm thời gian sau:
a) T(n) = 2n(n - 2) + 4.
b) T(n) = n3 + 5n - 3.