Câu hỏi về độ phức tạp của thuật toán lý thuyết

anh chị cho em hỏi tại sao T(n) = O(n) cũng có thể nói là T(n) = O(n^2) vậy ạ, em đọc mà thấy hơi khó hiểu ạ

O(n) \subset O(n^2):smiley:

f(n) \in O(n) \overset{\text{định nghĩa}}{\iff}\ \exists n_0\exists C>0, |f(n)| \leq Cn, \forall n \geq n_0

Ta chọn n_1 = max(1, n_0), với n\geq n_1 \geq 1 thì |f(n)| \cdot 1 \leq C\cdot n \cdot n = C \cdot n^2, suy ra f(n) \in O(n^2).

O(n) \neq O(n^2):
Phủ định:
f(n) \not\in O(n) \iff \forall n_0\forall C>0\ \exists n\geq n_0, |f(n)| > Cn
\forall n_0 > C, n_0^2 > Cn_0 nên n^2 \not\in O(n).

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