算法的时间复杂度

算法实际那复杂度定义

推导大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)。

线性阶

对数阶

平方阶