算法设计与分析【1】算法复杂度

时间:2024-04-13 17:06:43

算法复杂度

算法具有输入输出,有穷性,确定性,有限性;程序可以不满足有限性

大小关系对比

O(c)<O(logN)<O(log^2N)<O(N)<O(N*logN) < O(N^2)<O(N^3)<O(2^N)<O(N!)<O(N^N)
在对比时,其实也可直接对N带入具体值计算比较
算法设计与分析【1】算法复杂度

化简方法

1、用常数1取代运行时间中的所有加法常数C
2、保留最高阶项
3、如果最高阶项存在且不是1,去掉常数系数。比如5n^3我们取n^3,用大O表示结果

补充,有一些关于O的运算:
1、O(f+g)=O(f)+O(g)=O(max(f,g))
2、O(fg)=O(f)*O(g)
3、O(Cf(N))=O(f(N));C是正常数
4、f = O(f)

复杂度函数的基本推导过程

需要知道的公式:
算法设计与分析【1】算法复杂度

主要的方法有(主要掌握红色的方法):

算法设计与分析【1】算法复杂度
算法设计与分析【1】算法复杂度
算法设计与分析【1】算法复杂度算法设计与分析【1】算法复杂度算法设计与分析【1】算法复杂度

递归树的适用范围是问题规模以等比缩减的情况.
把非函数项作为根,把函数项作为根的儿子
每层节点的值就是当前迭代的非函数项的值
递归树的本质就是T(n)=树所有节点之和

算法设计与分析【1】算法复杂度
算法设计与分析【1】算法复杂度
算法设计与分析【1】算法复杂度
算法设计与分析【1】算法复杂度
算法设计与分析【1】算法复杂度
算法设计与分析【1】算法复杂度

参考

课程PPT
mooc算法设计与分析