Câu 1 tính độ phức tạp của các hàm số thời gian sau .a,T(n) bằng 2n(n-2)+4. b, T(n) bằng
Quảng cáo
3 câu trả lời 164
Để tính độ phức tạp của các hàm số thời gian, chúng ta thường tìm kiếm các yếu tố quyết định độ phức tạp như số lần lặp, số phép toán cơ bản, và chiều sâu của đệ quy (nếu có).
a) \( T(n) = 2n(n-2) + 4 \)
Trong hàm này, có hai phép toán nhân (nhanh chóng tăng theo quy mô của n), một phép toán trừ, và một phép toán cộng. Vậy độ phức tạp là \( O(n^2) \).
b) \( T(n) = \log_2{n} \)
Hàm này là hàm logarithm cơ số 2 của n. Logarithm là một hàm tăng chậm khi n tăng lên. Vậy độ phức tạp là \( O(\log{n}) \).
Trả lời
Thanhh Dienn
· 1 năm trước
a) T(n) = 2n (n-2) +4
= T(n) = 2n (n-2) +4
= 2n^2 - 4n +4
O ( T (n) ) = O ( max ( 2n^2 , -4n , 4 ) )
= O (2n^2 )
= O ( n^2 )
b ) T (n) = n^3 +5n - 3
T (n) = n^3 +5n -3
O ( T ( n) ) = O ( max ( n^3 , 5n , -3 ) )
= O (n^3)
a) T(n) = 2n (n-2) +4
= T(n) = 2n (n-2) +4
= 2n^2 - 4n +4
O ( T (n) ) = O ( max ( 2n^2 , -4n , 4 ) )
= O (2n^2 )
= O ( n^2 )
= T(n) = 2n (n-2) +4
= 2n^2 - 4n +4
O ( T (n) ) = O ( max ( 2n^2 , -4n , 4 ) )
= O (2n^2 )
= O ( n^2 )
Quảng cáo
Bạn cần hỏi gì?
Câu hỏi hot cùng chủ đề
-
Đã trả lời bởi chuyên gia
86047
Gửi báo cáo thành công!
