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

开发者社区> 云.智> 正文

常用算法和复杂度总结

简介: 一、常用算法和复杂度 算法 名称 复杂度 备注 快速排序 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方法

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

       利用对称性裁剪子树

       划分成子问题

分支策略

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

 

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

 

 

 

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

相关文章
算法:复杂度
我的程序会运行多长时间?为什么我的程序耗尽了所有内存? 时间复杂度 在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。 这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。
667 0
冰与火之歌:「时间」与「空间」复杂度 | 算法必看系列三十六
对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间; 反之,求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。
2251 0
【Java数据结构及算法实战】系列006:算法复杂度等级及其分析
在前一节,我们介绍了程序的性能,也介绍了评估性能的方式。那么,我们是否就能测算出算法需要运行的时间呢? 在上一节,我们了解算法复杂度的度量规则,接下来我们将学会如何对各个具体算法的复杂度进行分析。按照渐进复杂度的思想,可以将算法的复杂度按照高低划分为若干典型的级别。这种分类方法,也被称为**函数的界**或者**函数的阶**。
7 0
常用的消息摘要算法小总结
今天偶然的学习了一下几种关于消息摘要算法的知识。个人觉得很好。应着老话“好记性不如烂笔头”,我就码了几行代码咯。 算法嘛,没什么好说的了。毕竟是设计者智慧与汗水的结晶,也是时代进步的推动力。
1001 0
+关注
云.智
就职于阿里云数据库团队,花名云智,高级技术专家。此前从事过8年左右的信息安全产品的研发,涉及运维安全、网络安全和数据库安全等方向。对开源软件和技术,分布式系统、数据库和安全领域感兴趣。当前致力于构建高可用、高可靠、安全、稳定、大规模的云数据库系统,为用户提供开箱即用的数据库服务。
67
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载