算法的定义

算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,
并且每条指令表示一个或多个操作。
比如一个给定的问题:1+2+3+4...+99+100等于多少?
正常来说我们会写一个循环来得到结果:

sum = 0
for i in range(101):
    sum += i
print sum
>>> 5050

再来看看数学家高斯的算法思路:

n = 100
sum = (1 + n) * n / 2
print sum
>>> 5050

他用的方法相当于另一种求等差数列的算法。
相比之下,第二种算法不需要计算机循环一千,一万次的加法运算。

算法的特性

算法具有五个基本特性:输入,输出,有穷性,确定性和可行性。

  • 有穷性
    指算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每一个步骤在可接受的时间内完成。

  • 确定性
    算法的每一个步骤都具有确定的含义,不会出现二义性。算法在一定条件下,
    只有一条执行路径,相同的输入只能由唯一的输出结果。

  • 可行性
    算法的每一步都必须是可行的,也就是说,每一步都能够通过执行有限次数完成。

算法设计的要求

1)正确性

算法的正确性是指算法至少应该具有输入,输出和加工处理无歧义性,
能正确反映问题的需求,能够得到问题的正确答案。

2)可读性

算法设计的另一目的是为了便于阅读,理解和交流。
写到这里想起了部门老大推荐给我们的一篇文章:初级,中级和高级开发人员之间的差异
里面有一句话非常好:

程序语言不仅仅是给计算机看的,更多是给人看的。

3)健壮性

在输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果。

4)时间效率高,存储量低

时间效率是算法的执行时间,存储量是指算法在执行过程中需要的最大存储空间。
在生活中,人们都希望花做少的钱,用最短的时间,办最好的事情,算法也是一样的思路。

算法效率的度量方法

1)事后统计方法

通过设计好的测试程序和数据,对运行时间进行比较,从而确定算法效率高低。
但这种方法显然有很大的缺陷:

  • 必须事先依据算法编好程序,如果算法很糟糕,测试程序就是竹篮打水。
  • 时间的比较依赖计算机硬件和软件等环境因素,有时会掩盖算法本身的优劣。

  • 算法的测试数据设计困难,需要多少数据来测试很难判断。

2)事前分析估算方法

在计算机程序编制前,依据统计方法对算法进行估算。
经过分析,发现一个高级程序语言编写的程序在计算机上运行时所消耗的时间取决于以下因素:
1.算法采用的策略,方法。
2.编译产生的代码质量。
3.问题的输入规模。
4.机器执行指令的速度。


From zero to hero