草丁图书馆

  1. 首页 > 生活杂烩 >

时间复杂度怎么算，复合函数的时间复杂度怎么算( 四 )

小知识


for (i=1; i<=n; i++)
x++;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
x++;
第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2) 。
常见的算法时间复杂度由小到大依次为：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1) 。 Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间 。 计算机科学家普遍认为前者是有效算法，把这类问题称为P类问题，而把后者称为NP问题 。
这只能基本的计算时间复杂度，具体的运行还会与硬件有关 。
参考博客地址：

推荐阅读


上一篇：曲面屏怎么贴膜，如何贴曲面屏钢化膜

下一篇：退团怎么退，不想当团员了怎么退团