Đề bài
Phương án nào sau đây nêu đúng độ phức tạp của hàm thời gian $T\left( n \right) = 2{n^2}{\rm{*}}\left( {n - 2} \right) + 4$ ?
${\rm{O}}\left( 1 \right)$.
${\rm{O}}\left( n \right)$.
${\rm{O}}\left( {{n^2}} \right)$.
${\rm{O}}\left( {{n^3}} \right)$.
Đáp án đúng: D
Xem lời giải
Lời giải chi tiết
Sử dụng định nghĩa để tính O cho hàm T(n).
Ta có, $T\left( n \right) = 2{n^2}{\rm{*}}\left( {n - 2} \right) + 4 = 2{n^3} - 4{n^2} + 4 \le 2{n^3} + {n^3}{\rm{\;}}\forall n \ge 1$.
Hay, $T\left( n \right) \le 3{n^3},\forall n \ge 1$.
Do vậy, $T\left( n \right) = {\rm{O}}\left( {{n^3}} \right)$.