参考价值：未完结、臃肿、不完善、不建议参考使用

算法的定义

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列。并且每条指令表示一个或多个操作。

为什么要学习更加优秀的算法？

在此之前先讲一个伟大数学家高斯关于算法的故事：

据说18世纪生于德国小村庄的高斯，上小学的一天，课堂很乱，老师非常生气。于是老师在放学时，就要求每个学生都计算1+2+3+···+100的结果，谁先算出来谁先回家。

天才当然不会被这样的问题难倒，高斯很快就的处理了答案，是5050.老师非常惊讶，因为他自己也是通过1+2=3，3+3=6,6+4=10, ······，4950+100=5050这样算出来的，也算了很久很久，怕算错，还算了两三遍。可眼前这个少年，一个上小学的孩子为何可以这么快的得出结果？

高斯解释道：sum=1+2+3+···+99+100

​ sum=100+99+98+···+2+1

​ 2 x sum=101+101+101+···+101=101 x 100=10100

​ sum=5050

这里老师和高斯就用了两种算法：

老师的算法：

1
2
3
4
5
6
int sum=0,n=100;
for(i=1;i<=n;i++)
{
    sum=sum+i;
}
printf("%d",sum);

高斯的算法：

1
2
3
int sum=0,n=100;
sum=(1+n)*n/2;
printf("%d",sum);

很明显，高斯的算法比老师的算法要好得多，尤其是当n的值越来越大时，高斯的算法简直是对老师算法降维打击。

现在我们回到主题：为什么我们要学习更加优秀的算法？

很简单，节约算力。

众所周知，计算机的算力要远远强于人类。但如果把n的值换成100亿，计算机用老师的算法，我们用高斯的算法，谁算的更快呢？很显然我们能够轻松地在两三分钟内算出结果，而计算机很可能算一年也算不出来，甚至可能直接嗝屁。

所以说，一个优秀的算法能够让我们用有限的算力处理更复杂的问题，而且往往越秀的算法往往对垃圾算法是降维打击的。

算法的特性

算法有五个基本特性：输入、输出、有穷性、确定性和可行性

输入输出

  • 算法有零个或者多个输入

  • 算法至少有一个或者多个输出

    这个输出值可以是打印输出，也可以是返回一个或多个值。

有穷性

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

确定性

算法的每一步骤都具有确定的含义，不会出现二义性。

可行性

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

算法的设计要求

我们要尽可能地去写一些好的算法，然而什么是好的算法呢？

好的算法一般具有正确性、可读性、健壮性、时间效率高和存储量低的特点。

正确性

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

  • 算法正确性的级别：
    1. 算法程序的语法没有错误
    2. 算法程序对于合法的输入数据能够得到满足需求的输出结果
    3. 算法程序对于非法的输入数据能够给出错误说明
    4. 算法程序对于精心选择的、刁钻的测试数据都能给出满足需求的输出结果
  • 一般我们对算法正确性的要求？
    算法正确性的四个级别，第一层是最容易做到的，第四层是最难做到的。通常我们如果要写出第四层的算法会消耗大量的时间和精力。因此，综合考虑，一般情况下，我们把第三层作为一个算法是否正确的标准。

可读性

算法设计的另一目的是为了便于理解阅读和交流。

算法不仅需要让自己读懂，而且需要让别人读懂。

健壮性

健壮性指当输入数据不合法时，算法也能做出相应处理，而不是运行异常，或者输出莫名其妙的结果。

时间效率高和存储量低

好的算法应该具有时间效率高和存储量低的特性。

算法效率的度量方法

事后统计法

事后统计法是指通过设计好的程序和数据来对不同的算法进行测试，比较它们运行的时间的多少。

  • 事后统计法的缺点：
    1. 必须把算法写出来后才能直达票算法的效率，如果算法不符合要求，写算法花费的工夫就会竹篮打水一场空。
    2. 运行时间不完全依赖于算法，还和软件、操作系统、编译器等因素有关。甚至同一台计算机不同时候测试同一个算法，得到的运行时间也是不完全相同的，因为运行时间还和内存的占用情况相关。因此，测出的时间有时并不能反映什么。
    3. 算法的测试数据实际困难，不同算法间运行速度的差异往往与数据规模有关。比如果我们要将0随机数排序，那么无论我们用任何算法，运行时间几乎都差不多。而如果给一百万个随机数排列，不同算法之间差异会很大，而且有些算法对CPU相当不友好0.0!

事前分析估算法

  • 一个高级语言编译的程序运行时间取决于哪些因素？

    1. 算法采用的方法、策略
    2. 编译产生的代码的质量
    3. 问题的输入规模
    4. 机器执行指令的速度

函数的渐近增长

算法的时间复杂度

算法时间复杂度定义

推导大O阶方法

常数阶

线性阶

对数阶

平方阶

常见的时间复杂度

算法的空间复杂度