03时间复杂度
时间复杂度
函数中的常数和其他次要项常常可以忽略,而更应该关注主项(最高阶)的阶数
y=x*3+2x*2+6:最大次幂
时间频度:T(n)=y
时间复杂度:O(n)=O(x*3)
f(n):T(n)的同数量级函数
大小比较:
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
空间复杂度
需要的存储空间
函数中的常数和其他次要项常常可以忽略,而更应该关注主项(最高阶)的阶数
y=x*3+2x*2+6:最大次幂
时间频度:T(n)=y
时间复杂度:O(n)=O(x*3)
f(n):T(n)的同数量级函数
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
需要的存储空间