【黑马程序员】关于算法的一些基本概念.pdf

【黑马程序员】关于算法的一些基本概念 说起算法，很多小伙伴的第一感觉是： 哇，牛 逼~! 这种牛逼是完全凌驾在会敲各语言的 Hello World 的层面上 那么，算法到底是有多神秘，让很多小伙伴内心想去征服它，又畏惧她了！ ~ 我们今天大概来认识一下，神秘面纱的背后，究竟是个萝莉音，还是抠脚大汉音！ ~ 一、什么是算法 首先，我们来看看度娘的定义： 是不是觉得特别正派，嗯！ ~是的，很正派！ ~ 简化点： 算法是对特定问题求解步骤的一种描述，是独立存在的一种解决问题的方法和思想。它是指令 黑马程序员成都中心 编著 的有限序列，其中每一条指令表示一个或多个操作； 此外，成为一个算法需要满足以下条件或特性： （1）有穷性。一个算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。 （2 ）确定性。算法中每一条指令必须有确切的含义读者理解时不会产生二义性。并且，在任何条 件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。 （3 ）可行性。一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有 限次来实现的。 （4 ）输入。零个或多个的输入。 （5 ）输出。一个或多个的输出。 二、设计算法要求 通常设计一个 “好 ”的算法应考虑达到以下目标： （1 ）正确性。对于合法输入能够得到满足的结果；算法能够处理非法处理，并得到合理结果； 算法对于边界数据和压力数据都能得到满足的结果。 （2）可读性。算法要方便阅读，理解和交流，只有自己能看得懂，其它人都看不懂，谈和好 算法。 （3）健壮性。算法不应该产生莫名其妙的结果，一会儿正确，一会儿又是其它结果。 （4）高性价比，效率与低存储量需求。利用最少的时间和资源得到满足要求的结果，可以通 过 (时间复杂度和空间复杂度来判定 ) 同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算 法分析的目的在于选择合适算法和改进算法。 计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是 一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大 O 符号【 O 】表述，不包括这 个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大 小趋近无穷时的情况。 算法复杂度分为时间复杂度和空间复杂度。其作用：时间复杂度是指执行算法所需要的 计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体现在运行该算 法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂 度分为时间和空间复杂度）。 三、时间复杂度 （1）时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测 试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间 多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正 比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频 度或时间频度。记为 T(n) 。（算法中的基本操作一般指算法中最深层循环内的语句） 黑马程序员成都中心 编著 （2 ）时间复杂度 在刚才提到的时间频度中， n 称为问题的规模，当 n 不断变化时，时间频 度 T(n) 也会不断变化。 但有时我们想知道它变化时呈现什么规律。为此， 我们引入时间复杂度 的概念。 一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数， 用 T(n) 表示，若有某个辅助函数 f