锐客网

  1. 首页 > it技术 > >

算法设计与分析---论序

算法绪论 算法设计与分析主要的目的是让我们学会怎么设计高效的算法，分析算法的性能，并且两者交互验证。
什么是交互验证呢，就是在设计出算法的同时，能够分析出来算法的性能。
算法的由来 公元前300年，欧几里得的辗转相除法，算最大公约数。
算法最早出自周髀算经中，随着演进，在魏晋时期的九章算术的割圆术。
唐高宗时，总结出《算经十书》。
等等等等......随着演进，一直到图灵计算机的出现，是算法与计算机的结合。
算法的定义 生活中的算法，就像扑克牌的顺序，就是一种排序。
算法定义：

  • 给定数据输入，计算满足某种性质输出的问题
  • 给定计算问题，算法是一系列定义的计算步骤注意执行计算步骤，得出结果。
插入排序
【算法设计与分析---论序】将数组待排序元素依次插入到已排序的部分，使已排序的部分保持升序的性质
算法实例：
算法设计与分析---论序
文章图片

一组待排序，将24为已排序的部分，17跟24比较，17<24，将17往前提取。
算法设计与分析---论序
文章图片

然后一直循环，逐一插入,从而使数据规范化。
算法设计与分析---论序
文章图片

选择排序
算法设计与分析---论序
文章图片

简单来说，就是双指针，第一个指针指向的是顺序，第二个指针寻找最小的值，然后与第一个指针所指的值进行比较。
算法的性质
  1. 有穷性
    • 算法必须在有限个步骤后终止
  2. 确定性
    • 算法必须没有歧义，不能含糊不清
  3. 可行性
    • 可机械的一步一步执行基本操作步骤
算法的表示 自然语言
优势：贴近人类思维
机器语言
优势：精确表达逻辑，避免歧义。
劣势：不同编程语言，有差异。
伪代码
是一种更贴近自然语言，并且移植了编程语言的语法结构。
例如：
算法设计与分析---论序
文章图片

算法的分析 如何比较不同算法的性能呢，常言道：“快者为优，小者为胜。”算法的性能主要是从两个方面进行比较，一个是时间复杂度，一个是空间复杂度
算法分析的原则
由于计算机性能也会影响算法的运行速度，所以，统一机器性能后，算法运行时间便会依赖于算法的规模，同时，输入的情况也影响算法的时间。
在进行比较时，最好情况不具有普遍性，最坏情况确定上界，更具一般性。
一般情况分析复杂，分析难度大，所以分析时，要统一机器性能，同时分析最坏的情况，这时，输入规模T(n)是影响最大的。
算法分析工具
由于正常分析规模大，所以引进渐进分析。
渐进分析：
算法设计与分析---论序
文章图片

引入渐进分析后，我们在分析算法的时间复杂度时，只关注最高阶便可。
同时，渐进分为渐近上界，渐进下界，渐进紧确界。
算法设计与分析---论序
文章图片

算法分析实例
算法设计与分析---论序
文章图片

算法设计与分析---论序
文章图片

渐近上界是该曲线的最大值，也就是最坏情况下我们的取值。
算法设计与分析---论序
文章图片

一般用渐进上界来确定时间复杂度。
算法设计与分析---论序
文章图片

算法设计与分析---论序
文章图片

    推荐阅读


    上一篇：微服务7（通信之RPC）

    下一篇：iCloud开发:|iCloud开发: key-value Storage,CloudKit,iCloud Documents