时间复杂度
推导出时间复杂度呢?有如下几个原则:
如果运行时间是常数量级,用常数1表示。
只保留时间函数中的最高阶项
如果最高阶项存在,则省去最高阶项前面的系数。
例如:
1. T(n) = 3n
最高阶项为3n,省去系数3,转化的时间复杂度为:T(n) = O(n)
2. T(n) = 5logn
最高阶项为5logn,省去系数5,转化的时间复杂度为:T(n) = O(logn)
3. T(n) = 2
只有常数量级,转化的时间复杂度为:T(n) = O(1)
4. T(n) = 0.5n^2 + 0.5n
最高阶项为0.5n^2,省去系数0.5,转化的时间复杂度为:T(n) = O(n^2)
时间复杂度比较:O(1)< O(logn)< O(n)< O(n^2)