算法概述

什么是算法

什么是算法？算法就是解决问题的步骤。在计算机领域，算法能够帮助计算机解决特定的问题，例如：将随意排列的数字按从小到大排列、找出一组数据中数值最小的数据、找出出发点到终点的最短路径等等。同时算法是严密的，它的步骤能够用数学的方式去描述。

算法是以人类能够理解的方式去描述的，它不局限于某种语言。也就是说同一个算法，可以用不同的语言去实现（C++、Java、Python、Go等等），虽然写出来的程序各不相同，但是最终都能解决算法要解决的问题。

提起算法，必定会提起数据结构，那么数据结构和算法是什么关系？如果用一个公式来概括算法和程序的关系：数据结构 + 算法 = 程序。数据结构是组织数据的一种“方式”，而对算法来说，数据结构相当于一种工具，能让算法实现的更好，更容易得解决问题。

算法的作用

算法能够帮助计算机解决特定的问题，这些特定问题通常需要计算机执行一些复杂的命令才能解决。我们知道计算机擅长执行一些基本命令（“做加法”、“在指定内存保存数据”等等），算法能够将这些基本命令组合搭配起来，完成复杂的操作。

我们算法设计等同于构思如何搭配组合基本命令来让计算机解决复杂问题。

算法的衡量指标

解决一个问题，往往有多种算法可以实现，那么如何去考量这些算法之间的优劣呢？在算法的评判上，考量的标准各有不同，但大致可以从两个角度去考量：时间和空间。不过，一般来说最为重视的是算法的运行时间，既从输入数据到输出结果所花费的时间，这是衡量算法的一个重要的指标，也是衡量的核心指标之一。

衡量算法的标准

1. 时间复杂度 ：大概程序要执行的次数，而非执行的时间。
2. 空间复杂度 ：算法执行过程中大概所占用的最大内存。
3. 难易程度
4. 健壮性

评估算法的核心指标有：时间复杂度、额外空间复杂度、常数项时间。

额外空间复杂度：要实现一个算法流程，在实现过程中，需要开辟一些空间来支持算法的实现。注意，和实现目标有关的空间不属于额外空间，例如作为输入参数的空间、作为输出结果的空间，这些都不算额外空间。除此之外，流程中还需要开辟空间的空间就是额外空间。如果流程中只需要开辟有限几个变量，额外空间复杂度就是O(1)。

最优解

笔试、面试中一个问题的最优解，一般情况下，是指时间复杂度尽可能的低，在满足了时间复杂度最低的指标下，使用最少的空间的算法流程，这个就叫问题的最优解。

对数器

用来校验算法流程是否可行的一个工具，简单来说就是在自己生成测试用例，然后将校验的算法与一个绝对正确的算法进行比较对数。

编写的流程：

1. 你要测的方法a
2. 实现复杂度不好但容易实现的方法b
3. 实现一个随机样本产生器
4. 把方法a和方法b跑相同的随机样本，看看得到的结果是否一样
5. 如果有一个随机样本使得对比结果不一致，打印样本进行人工干预，改对方法a和方法b
6. 当样本数量很多时对比测试依然正确，可以确定方法a已经正确