时间复杂度的计算

March 12, 2020 数据结构 访问: 26 次

  1. 找出算法中的基本语句;
    算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。
  2. 计算基本语句的执行次数的数量级;
    只需保留f(n)中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。
  3. 用大Ο记号表示算法的时间性能
    将基本语句执行次数的数量级放入大Ο记号中。

时间复杂度分析的基本策略是:从内向外分析,从最深层开始分析。如果遇到函数调用,要深入函数进行分析。

常见的算法时间复杂度由小到大依次为:
Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n²)<Ο(n³)<…<Ο(2^n)<Ο(n!)<O(n^n)

添加新评论