原文地址

1
2
3
https://baike.baidu.com/item/%E7%AE%97%E6%B3%95%E5%A4%8D%E6%9D%82%E5%BA%A6

https://blog.csdn.net/qq_41523096/article/details/82142747

时间频度

T(n)

算法中的语句执行次数称为语句频度或时间频度

时间复杂度(渐进时间复杂度)

O(f(n))

若存在函数 f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称 f(n)是T(n)的同数量级函数
直白的说,时间复杂度就是把时间频度T(n)简化为一个”数量级”
例如

  1. T(n) = n^2+3n+4与T(n) = 4n^2+2n+1它们的频度不同，但时间复杂度相同，都为O(n^2)
  2. T(n) = 3n,最高阶项为3n，省去系数3，转化的时间复杂度为:T(n) = O(n)
  3. T(n) = 5logn,最高阶项为5logn，省去系数5，转化的时间复杂度为T(n) = O(logn)