常用算法和复杂度总结-阿里云开发者社区

开发者社区> 人工智能> 正文

常用算法和复杂度总结

简介: 一、常用算法和复杂度 算法 名称 复杂度 备注 快速排序 QuickSort(A,p,r) 最坏:O(n2) 平均:O(nlog n) 均衡划分:O(nlog n) ...

一、常用算法和复杂度

算法

名称

复杂度

备注

快速排序

QuickSort(A,p,r)

最坏:O(n2)

平均:O(nlog n)

均衡划分:O(nlog n)

 

合并排序

MergeSort(A,p,r)

O(nlog n)

 

选最大

FindMax

O(n)

 

选最大和最小

FindMaxMin

W(n)=3n/2-2=O(n)

 

找第二大

锦标赛法

n+logn-2

 

选择第k

Select

O(n)

 

动态规划:矩阵连乘

MatrixChain(P,n)

递归:O(2n)

非递归:O(n3)

 

动态规划:投资问题

 

O(nm2)

m元钱投资n个项目

动态规划:背包问题

 

 

目标函数、约束条件、递推方程

动态规划:最长公共子序列

LCS_length(X,Y)

LCS(B,i,j)

W(mn)=O(mn)

S(mn)=O(mn)

 

动态规划:图像压缩

Compress(P,n)

T(n)=O(n)

 

动态规划:最大子段和

 

顺序:O(n3)

分支策略:O(nlog n)

动态规划:O(n)

 

动态规划:凸多边形的三角划分

 

时间O(n3),空间O(n2)

 

动态规划:电路布线

MNS(C,n)

T(n)=O(n2)S(n)=O(n2)

 

动态规划:最优二叉搜索树

 

T(n)=O(n2)S(n)=O(n2)

 

贪心法:活动选择问题

Greedy Select

 

 

贪心法:最优装载问题

Loading

O(nlogn)

 

贪心法:最小延迟调度问题

 

O(n)

 

贪心法:找零钱问题

 

 

 

贪心法:装箱问题

 

 

 

贪心法:最优二元前缀码问题

HuffmanC

O(nlogn)

 

贪心法:文件归并

Huffman算法

O(nlogn)

 

贪心法:最小生成树

kruskal算法

O(nlogn)

 

贪心法:单源最短路径

Dijkstra算法

O(n2)

 

回溯法:四后问题

递归回溯,迭代回溯

四叉树,深度优先

指数级,蒙特卡罗法估计效率

 

回溯法:最有装载问题二

子集数,深度优先

指数级

 

分支估界:背包问题

代价函数,深度优先

           

 

分支估界:最大团问题

子集树

代价函数:F=Cn+n-k

约束条件

O(n2n)

 

回溯法:图的m着色问题

 

O(nmn)

 

分支估界:巡回售货员问题

 

O(n!)

 

分支估界:圆排列问题

 

O((n+1)!)

 

分支估界:电路板排列问题

 

O(mn!)

 

分支估界:连续邮资问题

 

指数级

 

 

二、动态规划算法

设计步骤:

1)  将问题表示成多步判断

2)  确定是否满足优化原则---必要条件

3)  确定子问题的重叠性---估计算法效率

4)  列出关于优化函数的递推方程(或不等式)和边界条件

5)  自底向上计算子问题的优化函数值---非递归的算法

6)  备忘录方法记录中间结果

7)  标记函数追踪问题的解

问题:

1)  时间复杂性改进依赖于子问题的重叠程度

2)  空间复杂度较高

 

三、贪心算法

设计要素:

       1)适用于满足优化原则的组合优化问题

       2)将问题表示成多步判断

       3)确定一个优化测度---贪心选择的依据

       4)确定是否满足贪心选择性质---每步贪心选择都会导致最优解

       5)自顶向下计算

贪心算法正确性的证明思路:

数学归纳法,叙述一个可以归纳证明的命题,并证明。

1)  对步数k归纳

对于任意kk步贪心选择得到i1i2ik,那么存在最优解包含i1i2,。。。,ik

2)  规模k归纳

对于任意k,贪心法得到关于规模为k的问题的最优解。

四、回溯法和分支估界法

适用于求解组合搜索和优化问题

求解条件:满足多米诺性质

解的表示:解向量,求解是不断扩充解向量的过程

回溯条件:

       搜索问题---约束条件

       优化问题---约束条件+代价函数

算法复杂性:

       遍历搜索树的时间,最坏情况为指数,空间代价小

平均时间复杂性的估计:Monte Carlo方法

降低时间复杂性的主要途径:

       利用对称性裁剪子树

       划分成子问题

分支策略

       深度优先、宽度有限、宽深结合、优先函数

 

五、求解组合优化问题的算法设计技术比较

 

 

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章