为什么要学算法和数据结构？
也许对于crud开发者，数据结构和算法毫无用处。但是面对业务量非常大的系统，用不同的算法和数据结构跑出来的功能，性能差距会比较大，当整个项目都是一堆垃圾代码的时候，第一, 业务执行效率低，直接导致用户体验不好。第二，执行占用的内存资源很多，需要更多的硬件资源支撑，扩展了说，也需要花更多的精力去维护这些硬件资源的稳定性。
数据结构与算法的关系
数据结构跟算法相辅相成，数据结构为算法服务，算法要作用在具体的数据结构上。
就好比一个俄罗斯方块的游戏，数据是每次掉下来的砖，数据结构是砖的形状，算法是你怎么把他们叠一起。
重要概念 -- 复杂度分析
数据结构与算法的根本
在资源层面来看：
数据结构 -- 空间
算法 -- 时间
在软件工程层面来看：
时间 ＝ 效率
空间 ＝ 资源
学好数据结构和算法，最终目的就是能在时间和空间之间寻找合理的平衡点。所以面对很多优化问题的时候，根本思想就两点：
1.时间换空间
2.空间换时间
当然 在对面时间和空间的取舍问题时，先得把时间（算法）、空间（数据结构）给整明白了，才能在取舍问题上做文章。最终来优化我们的项目和代码。
所以复杂度分析，就是针对时间和空间的分析。
为什么需要复杂度分析？
- 功能测试对场景的要求太多，不同场景需求对 用不同数据结构和算法的 实现，测试结果的性能不一。换个角度说，同一数据结构和算法 在不同场景下表现的性能不一，所以，我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。
复杂度分析之具体落地 -- 大O复杂度表示法
例：
int cal(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum = sum + i * j;
}
}
}
上述代码，假设方法体里CPU的一次 读数据-运算-写数据 (一次完整的运算) 的执行时间为 X，那么总时间就是
3X ＋ nX ＋ n2nX ＝ （3＋n＋2n²）X ＝ T(n)
【注：这里的2n是因为 i*j是一个运算，sum＋x是一个运算】
这样我们可以发现 所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。
定义公式： T(n) ＝ O(f(n))
其中，T(n) 表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。
所以 上面例子可以表示成 T(n) ＝ O(3＋n＋2n²) 当n的数量级很大时候，可以简化为T(n)＝O(n²) 【注：大 O 这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。】
这里面 的 O 当n是常量时，这里面的 代码的执行时间是确定的，但是 在实际场景中，数据规模n是不随随机的，所以需要用O来动态表示 代码执行时间随数据规模变化的趋势。 也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
时间复杂度分析
时间复杂度之用关注执行次数最多的代码 （这里会有一个问题，就是如果一个方法体内，有几个关于数据体量，且执行过程互不干涉的内容，根据数据体的不同，执行的效果也可能不同，也就是不能确定哪个是最多的）
加法法则：总复杂度等于量级最大的那段代码的复杂度
例：
int cal(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
sum_1 = sum_1 + p;
}
int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum_3 = sum_3 + i * j;
}
}
return sum_1 + sum_2 + sum_3;
}
如1所说，这个例子就是 第一段为O（1） ，第二段为O（n），第三段为 O（n²），
所以可以表示为 O（max(n,n²)） 【注：此处是举个例子理解加法运算，在此案例中实际n是大于等于1的 ，所以肯定是O（n2）】
3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
这一点很好理解，嵌套的执行都是这样。
常见的时间复杂度
- O(1)
因为时间复杂度表示的是一种趋势，对这种趋势的细节不太关注 ，所以 ，用次思想来看待 O(1)，O(2)，O(3) ，都可以认为是 O(1)。
所以，一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。
- O(logN)
对数阶时间复杂度非常常见，如下：
i=1;
while (i <= n) {
i = i * 2;
}
此例中 T(n) ＝ x² 也就是时间复杂度为O(log2 N) 以2为底 N的对数
在采用大 O 标记复杂度的时候，可以忽略系数，O(log2n) 就等于 O(logn)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。
理解了O(logn)，那 O(nlogn) 就很容易理解了。结合乘法法则，如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。
- O(m+n)、O(mn)
当数据不只有一个时，时间复杂度就需要根据每个数据体量变量来计算，所以当加法时候，需要表示为O(m＋n) 。乘法时需要表示成 O(mn)
空间复杂度分析
类比时间复杂度，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。
例：
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}
for (i = n-1; i >= 0; --i) {
print out a[i]
}
}
此代码的空间复杂度就是O(n)。
常见的空间复杂度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。
常见复杂度曲线关系
复杂度分析 -- 方法论
四个角度：
最好情况时间复杂度（best case time complexity）
顾名思义，假设情况最完美;
例如一个数组中找到某个数并返回，那个数就在数组的第一个位置。所以最好情况就是O(1)
最坏情况时间复杂度（worst case time complexity）
假设情况最完美;
例如一个数组中找到某个数并返回，那个数就在数组的最后一个位置。所以最坏情况就是O(n)
平均情况时间复杂度（average case time complexity）
最好和最坏是两种极端且特殊的情况，不能衡量整体情况，这时候就需要取平均值：
要查找的变量 x 在数组中的位置，有 n+1 种情况：在数组的 0～n-1 位置中和不在数组中。如果结果会根据数据的权重而变化，此时算平均情况时间复杂度便需要加上数据的权重。
实际上，在大多数情况下，我们并不需要区分最好、最坏、平均情况时间复杂度三种情况。很多时候，我们使用一个复杂度就可以满足需求了。只有同一块代码在不同的情况下，时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分。
例：
// array 表示一个长度为 n 的数组
// 代码中的 array.length 就等于 n
int[] array = new int[n];
int count = 0;
void insert(int val) {
if (count == array.length) {
int sum = 0;
for (int i = 0; i < array.length; ++i) {
sum = sum + array[i];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
对每一次调用而言，这里最好情况就是 不走if里面，所以是O(1)，最坏的情况是走if里面所以是O(n)）。平均复杂度就是 （ O(1)*（n-1）＋O(n) ) /n ，所以是O(1)。
均摊时间复杂度
基于上面那两个例子，当每次调用的时间复杂度都很不确定的情况下，可以用平均复杂度来判定，但是下面数组插曲的例子，此时我们的调用，大部分情况下时间复杂度都是比较低的，只有很少的情况比较高，此时可以把较高的操作的复杂度平摊到其他低的上面，其实也就是一种特殊的平均时间复杂度。一般均摊时间复杂度等于最好情况复杂度。
实际项目中 时间复杂度应该调用执行的角度去分析，而不是调用数据的大小来分析。譬如数据大小可能是1到10，但是调用操作大部分数据都是以2为入参，我们就不能简单的只分析数据层面的时间复杂度。
