第五课 算法的时间复杂度

  判断一个算法的效率时,操作数量中的常数项和其他次要项常常可以忽略,只需要关注最高阶项就能得出结论。

如何用符号定性的判断算法的效率呢?

  算法的复杂度:

时间复杂度:

  算法运行后对时间需求量的定性描述。

空间复杂度:

  算法运行后对空间复杂度的定性描述。

数据结构课程重点关注的是算法的效率问题,因此,整个课程会集中的讨论算法的时间复杂度,但其使用方法完全可以用于空间复杂度的判断。

大O表示法:

常见的时间复杂度:

线性时间复杂度:

对数阶时间复杂度:

平方阶时间复杂度:

下面代码片段的时间复杂度是什么:

练习1:

练习2:

func函数的时间复杂度是O(n*n)。

练习3:

test函数的时间复杂度为O(n*n*n)。

总结:

  时间复杂度是算法运行时对于时间的需求量

  大O表示法用于描述算法的时间复杂度

  大O表示法只关注操作数量的最高次项

  常见的时间复杂度为:线性阶、平方阶和对数阶。

原文地址:https://www.cnblogs.com/wanmeishenghuo/p/9495958.html