常数时间的操作

一个操作如果和样本的数据量没有关系，每次都是固定时间内完成，叫做常数操作。

时间复杂度

时间复杂度为一个算法流程中，常数操作数量的一个指标。用 O（读作 big O）来表示。具体来说，要先对一个算法流程非常熟悉，然后计算这个算法流程中，发生了多少常数操作，进而总结出常数操作数量的表达式。

在常数操作数量表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分设为 f(N)，那么时间复杂度为 O(f(N))。

常见的时间复杂度

image-20201219085403664.png
大小关系
image.png

空间复杂度

空间复杂度的分析可以有以下三步：

  1. 找到所占空间大小与问题规模相关的变量
  2. 分析所占空间 x 与问题规模 n 的关系 x = f(n)
  3. x 的数量级 O(x) 就是算法空间复杂度 O(n)

关于复杂度的计算可以在做题过程中慢慢练习，个人感觉除了 DFS 等一些递归调用很多的算法，复杂度还是很好看出来的。

原地算法的概念

in-place 算法，称为原地算法，根据 WIKI 的解释：

In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output as the algorithm executes. In-place algorithm updates input sequence only through replacement or swapping of elements. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.

原地算法要求不使用额外的数据结构，但是可以使用辅助变量来保留少量的额外空间，算法执行时，通过替换和交换的方式来更新原始的输入。