本节虽然名为“算法”，其实讲的只是算法的一些概念以及评估方式，并没有涉及很复杂的算法。
解决问题：
- 什么是算法
- 算法的特性
- 算法设计的要求
- 如何评估一个算法的优劣
通过本节的学习，我们可以轻松的解决这些问题。
1.算法的概念
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
通俗的讲，算法就是解决问题的步骤。很多优秀的算法都是前人不断的总结，积累下来的求解特定问题的步骤。
我们在上一节中提到了
程序设计 = 数据结构 + 算法
那么算法与数据结构的关系就像梁山伯与祝英台，罗密欧与朱丽叶。数据结构和算法可以单独列出来讲解，但是把他们放在一起才会感受到前人的智慧。
2. 两种简单算法的比较
为了更加直观的感受到什么是算法，我们来举一个小例子。
问题：
计算 1+2+3+......+100 的和。
有些朋友该说了，这不是太简单了吗，不管使用哪种语言，都会很容易的想到这种简单的写法，在编译器立马写下如下代码：
(这里使用swift语言)
// 计算1到100的和
var sum = 0, n = 100
for i in 1...n {
sum += i
}
print("sum = \(sum)")
很容易看明白吧。这其实也是一种算法，他就是一种解决求和问题的算法，至于优劣，我们后来再讨论。
我们这里插述一个大数学家高斯的故事。
高斯小时候，又一次老师出了一个题目，让同学们计算 1到100的和，就是上面我们解决的那个问题。高斯很快就计算出了结果，他是如何快速计算出结果的呢？
sum = 1 + 2 + 3 + ......+100
sum = 100 + 99 + 98 + ......+ 1
sum + sum = 101 + 101 + 101 + ......+101
共有 100个101 。
所以，
sum = (1 + n) * n / 2
上述的算法改进之后就变成了：
// 优化
var sum2 = 0, n2 = 100
sum2 = (1 + n2) * n2 / 2
print(sum2)
这样计算是不是快了很多？
3. 算法的特性
算法具有五个特性：
输入、输出、有穷性、可行性、确定性。
输入：
算法具有0个或者多个输入。
输出：
算法至少有一个输出。
有穷性：
算法必须会自动结束并且在可接受的时间范围内。
可行性：
算法的每一个步骤都是可行的，每一步都通过执行有限次数完成。
确定性：
相同的输入，只有唯一的输出结果。
4. 算法的设计要求
正确性、可读性、健壮性、时间效率高、存储量小。
正确性：
算法必须是正确的，能够解决问题，得到问题的正确答案。
可读性：
算法应该是便于阅读交流和理解的。
健壮性：
对于异常情况，都要有很好的兼容性。
时间效率高：
执行时间越短的算法越好。
存储量低：
占用内存越小的越好。
5. 算法效率的度量方法（时间复杂度）
算法的效率度量有两种方式：
- 事后统计方法
- 事前分析估算方法
事后统计方法：
通过设计好的测试程序和数据，利用计算机计时器对不同的算法运行时间进行比较，从而确定效率的高低。
这是一种很不精确的度量方式，误差会很大。
为什么？
因为这样的话，需要事前编制测试程序，花费大量的精力，如果算法不好，则又是白费力气。且时间的计算依赖计算机的硬件以及软件，计算机的软硬件是有差别的，而且运行不同的程序也会导致结果的不同。
事前分析估算方法
这是一种很科学的计算方式。
它是在计算机程序编制之前，依据统计方法对算法进行估算。
程序在计算机上运行所消耗的时间取决于以下的因素：
1.算法的策略（算法好坏的根本）
2.编译产生的代码量（编译器决定）
3.问题的输入规模
4.机器执行指令的速度（硬件性能）
所以，一个程序的运行时间，依赖于算法的好坏和问题的输入规模。
我们还来看之前的求和的例子：
var sum = 0, n = 100 ……执行 1 次
for i in 1...n { …..…………执行 n + 1次
sum += i ……... …………执行 n 次
}
print("sum = (sum)") ……执行 1 次
执行次数是
1 + （n +1） + n + 1 = 2n + 3 （次）
第二种算法
var sum2 = 0, n2 = 100 ············执行1次
sum2 = (1 + n2) * n2 / 2············执行1次
print(sum2)····························执行1次
执行次数是
1 + 1+ 1 = 3 （次）
显而易见，那种算法效率更高。
测定运行时间最可靠的方法就是计算运行时间有消耗的基本操作的执行次数，运行时间与整个次数成正比。
时间有限，本节暂时记录这些内容，下一篇文章中我们一起学习算法中函数的渐进增长、算法的时间复杂度、算法的空间复杂度等内容。
一起加油吧。
网友评论