算法实际那复杂度定义

推导大O阶

  • 1.用常数1取代运行时间中的所有加法常数。
  • 2.在修改后得运行次数函数中,只保留最高阶项 。
  • 3.如果最高阶项存在且不是1,则去除与这个项相乘的常数。
  • 得到的结果就是大O阶

常数阶

1
2
3
int sum = 0,n=100;    /* 执行一次 */
sum = (1+n)*n/2;      /* 执行一次 */
printf("%d", sum);    /* 执行一次 */

这个算法运行次数函数是f(n)=3.根据我们推到大O阶的方法,第一步就是把常数项3改为1。在保留最高阶项时发现,它根本没有最高阶项,所以这个算法的时间复杂度为O(1)。

线性阶

对数阶

平方阶