【学习笔记】【数据结构与算法篇】复杂度分析

复杂度分为两类：时间复杂度和空间复杂度

我们为什么需要复杂度：用来衡量执行一个算法时，数据规模与时间和空间的关系

那什么是复杂度？怎么定义？：

时间复杂度：定性描述算法运行时间的函数

空间复杂度：对一个算法在运行过程中临时占用存储空间大小的量度

请注意，是定性描述。

表示方法： 用 big O 表示法表示，形如 O(n²)

时间复杂度量级：

• 常数阶 O(1)
• 对数阶 O(logn)
• 线性阶 O(n)
• 线性对数阶 O(nlogn)
• 平方阶 O(n²)
• 立方阶 O(n³)
• k次方阶 O(n^k)
• 阶乘阶 O(n!)
• 指数阶 O(2ⁿ)

对时间复杂度，可以理解为每行代码执行时间都是单位时间，执行次数就是数据量，从而知道执行次数，就能知道复杂度。

比如，下面这段：

i=0
j=0
a=i+j

执行了三次，用 big O 表示法表示为 O(1)，因为 3 是常数，这是常数阶的时间复杂度。

而下面这段

// input n

int sum=0;

for (i=0;i<n;i++) {
    sum+=i
}

这里，n 是输入的一个数，代码的执行次数随着 n 的增大而增长，这是一个线性时间 O(n)。

时间复杂度还分：

• 最好: 代码在最理想情况下执行的时间复杂度
• 最坏: 代码在最坏情况下执行的时间复杂度
• 平均: 用代码在所有情况下执行的次数的加权平均值表示
• 均摊: 在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度

空间复杂度类似，就是算法存储空间与数据量的关系，不赘述