复杂度

时间复杂度和空间复杂度

前置知识：选择排序、冒泡排序、插入排序、等差数列、等比数列建议：不要跳过 1，常数操作，固定时间的操作，执行时间和数据量无关

2，时间复杂度，一个和数据量有关、只要高阶项、不要低阶项、不要常数项的操作次数表达式
举例：选择、冒泡、插入

3，严格固定流程的算法，一定强调最差情况！比如插入排序

4，算法流程上利用随机行为作为重要部分的，要看平均或者期望的时间复杂度，因为最差的时间复杂度无意义
用生成相邻值不同的数组来说明

5，算法流程上利用随机行为作为重要部分的，还有随机快速排序（【必备】课）、跳表（【扩展】课）也只在乎平均或者期望的时间复杂度，因为最差的时间复杂度无意义

6，时间复杂度的内涵：描述算法运行时间和数据量大小的关系，而且当数据量很大很大时，这种关系相当的本质，并且排除了低阶项、常数时间的干扰

7，空间复杂度，强调额外空间；常数项时间，放弃理论分析、选择用实验来确定，因为不同常数操作的时间不同

8，什么叫最优解，先满足时间复杂度最优，然后尽量少用空间的解

9，时间复杂度的均摊，用动态数组的扩容来说明（等比数列、均摊的意义）并查集、单调队列、单调栈、哈希表等结构，均有这个概念。这些内容【必备】课都会讲

10，不要用代码结构来判断时间复杂度，比如只有一个while循环的冒泡排序，其实时间复杂度O(N^2)

11，不要用代码结构来判断时间复杂度，比如：N/1 + N/2 + N/3 + … + N/N，这个流程的时间复杂度是O(N * logN)，著名的调和级数

12，时间复杂度只能是对算法流程充分理解才能分析出来，而不是简单的看代码结构！这是一个常见的错误！甚至有些算法的实现用了多层循环嵌套，但时间复杂度是O(N)的。在【必备】课程里会经常见到

13，常见复杂度一览： O(1) 常数 O(logN) 二分，以2为底，长度为几砍几次 O(N) 过数组有限几遍 O(N*logN) 调和级数，归并，快排，堆排 O(N^2) … O(N^k) O(2^N) … O(k^N) 递归 … O(N!) 阶乘

14，时间复杂度非常重要，可以直接判断某个方法能不能通过一个题目，根据数据量猜解法

S = n / 2 * (2 * a1 + (n-1) * d ) S = 其中，S 是等差数列的和；n 是项数；a1 是首项；d 是公差。也可以认为任何等差数列的都符合： a * n 平方 + b * n + c，其中 a、b、c 都是常数

$a \cdot n^2 + b \cdot n + c$ 去除低阶项，去除常数项为 $n^2$ O是趋近于哪个级别的意思

等差数列就是 $O (n^2 )$

数组寻找最大值 O(n)

常数操作O(1)

1 + 1/2 + 1/3 + 1/4 + ... 1/N = O（log n）调和级数

n/1 + n/2 + n/3 + n/4 + ... n/N = O（n * log n）调和级数

常数时间的速度：位》算术》寻址》哈希非常数时间：链表的get(i)方法

算法分类：说一个我觉得比较有趣、有用的算法分类

硬计算类算法、软计算类算法注意：这两个名词都不是计算机科学或算法中的标准术语

那为啥要提这个呢？因为很有现实意义。

硬计算类算法：精确求解。但是某些问题使用硬计算类的算法，可能会让计算的复杂度较高大厂算法和数据结构笔试、面试题、acm比赛或者和acm形式类似的比赛，考察的都是硬计算类算法。

软计算类算法：更注重逼近解决问题，而不是精确求解。计算时间可控比如：模糊逻辑、神经网络、进化计算、概率理论、混沌理论、支持向量机、群体智能

硬计算类算法是所有程序员岗位都会考、任何写代码的工作都会用到的。前端、后端、架构、算法所有岗位都要用到。但是算法工程师除了掌握硬计算类的算法之外，还需要掌握软计算类的算法。

说一个我觉得比较宏观的数据结构分类

任何数据结构都一定是这两个结构拼出来的！没有例外！

数据结构太多了，从链表、队列、栈，到可持久化线段树、树链剖分、后缀数组等等结构