01 算法基础
什么是数据结构？
数据源的结构就是数据结构，比如数组、二叉树、矩阵
什么是算法？
给你一个数据源，让你在数据源上完成一定的功能，你设计的流程就是算法。
算法的特点
- 一个有限指令集;
- 接受一些输入(有些情况下不需要输入);
- 产生输出;
- 一定在有限步骤之后终止;
- 每一条指令必须有充分明确的目标，不可以有歧义；
- 计算机能处理的范围之内;
- 描述不应该依赖于任何一种计算机语言以及具体的实现手段。
怎样评价一个算法的好坏
首先，这个算法必须是正确的，其次好的算法应该是友好的，便于人们理解和交流，并且是机器可执行的。这个算法还需要足够健壮，即当输入的数据非法或不合理时，也能适当的做出正确的反应或进行相应的处理，最后它还必须拥有高效率和低存储量要求。也就是所谓的时间复杂度和空间复杂度。
什么是复杂度
操作的代价（时间或空间）用与数据量有关的公式来表示，表示出来的式子不要低阶项，不要常数项，也不要高阶项的系数，剩下的部分称之为复杂度。
什么是常数操作
完成操作的代价（时间或空间）与数据量无关，一个固定的值，固定的代价。比如获得数组中的某个位置上的元素以及进行比较操作
什么是时间复杂度
一个流程中常数操作的数量，写成一个与数据量有关的表达式。该表达式中不要低阶项，不要常数项，也不要高阶项的系数，剩下的部分就是时间复杂度。O指的是整个过程收敛在这个评价标准内，若与数据量无关，那么就是O(1)。
什么是O
一个算法流程中，常数操作数量的指标，这个指标叫做O big O，具体为，如果常数操作数量的表达式中只要高阶项，不要低阶项，也不要高阶项系数之后，剩下的部分记为f(N)，那么该算法的时间复杂度为O(f(N))。
普遍认为O(N^2) 的算法要优于 O(N^3)的算法。如果最高阶的次数相等，那么最高阶系数越低，认为流程越优良。
在复杂度的学习中，如果不强调说明，那么logN就是指以2为底的对数。
什么是最优解
最优解表示在先满足时间复杂度最优的情况下，使用最小的空间。
案例
对于同一问题的不同算法分析其时间复杂度
什么是空间复杂度
一般是指额外空间复杂度，为了支持完成流程所需要的辅助空间。输入数组不算额外空间， 输出空间不算额外空间。 如果一个流程消耗的时间是与数据量的一次方成正比，那么就说这个流程的数据复杂度是O(N)的。如果使用的额外空间与数据量没有关系那么就称为O（1）（表示使用常数量级别的额外空间）
案例
对于同一问题的不同算法分析其空间复杂度
对数器
定义：你写了一个流程，你想知道他对不对，那你会依赖OJ（online judgement），OJ存在几个问题，第一，OJ这是一种非常偷懒且不好用的方法，首先要知道这个题的OJ在哪儿，其次，OJ的测试用例可能也不全。这个时候可以使用对数器。
思想：我们有一个流程很精妙，时间复杂度很低，但是容易出错的版本，还有一个容易写且不出错但复杂度高的版本。我们在程序中生成随机数据，让这两个流程来执行，比对这两个结果，如果跑了很多次都没有出错，我们就可以认为这两个流程都说是对的。如果发生了错误，我们就要看看是哪个出错了，然后修改，直到两个流程都不出错为止。
应用：在贪心算法中，我们可以直接全部枚举，这个方法最慢，但是可靠性最高，但是这个方法会非常耗时，提交代码会超时，那么我们可以在本地那我们写的算法与直接枚举的方法跑对数器，来检查我们的代码是否正确。