算法时间复杂度和空间复杂度

这是我参与更文挑战的第 16 天，活动详情查看: 更文挑战

序言

虽然做了多年 coding 工作，但是谈起算法还是觉得离自己很远，似乎没有算法也可以写出能够满足用户需求的程序。不过最近觉得自己这样下去很难有所提升，所以准备开始刷题。

开始刷了点 LeetCode 的题，感觉有点无从下手，不知所措的感觉。为此决定还是从基础开始吧，先看数据结构。那么我们算法除了实现一些方法，而且更多会考虑时间和空间资源上销毁

基本信息

什么是算法

算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题，可能会有多种不同的算法来给出正确答案，但在过程中消耗的资源和时间却会有很大的区别。这也就是我们研究算法的目的。

时间复杂度和空间复杂度

• 时间复杂度：是指执行当前算法所消耗的时间。
• 空间复杂度：是指执行当前算法需要占用多少内存空间。

因此，评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而，有的时候时间和空间却又是鱼和熊掌，不可兼得的，那么我们就需要从中去取一个平衡点。

语言

准备提供这些语言版本关于问题的解决方案。

• javascript
• java
• python
• go
• rust
• cpp

时间复杂度

平时优化 code 时，我通常是在代码段前后输出时间来计算方法的耗时，认为这就是算法消耗的时间。不过我们这种优化的前提是我们使用的同样硬件配置，因为这个算法更多是因为硬件支持。其实我们是有一套尺度来衡量我们算法。

因此，另一种更为通用的方法就出来了：**大O符号表示法 **，即 T(n) = O(f(n))

const n = 10;
var j = 0;
for(let i=1; i<=n; ++i)
{
   j = i;
   j++;
}
复制代码

通过大 O 符号表示法，这段代码的时间复杂度为：O(n) ，为什么呢?

复杂度量级

常见的时间复杂度量级有：

• 常数阶O(1)
• 对数阶O(logN)
• 线性阶O(n)
• 线性对数阶O(nlogN)
• 平方阶O(n²)
• 立方阶O(n³)
• K 次方阶O(n^k)
• 指数阶(2^n)

const N = 10;
var a = 0;
var b = 0;
for (let i = 0; i < N; i++) {
    a = a + Math.random()    // $N \times 1$ 操作 = O(N)
}
复制代码

for (let i = 0; i < N; i++) {
    a = a + Math.random()    // $N \times 1$ 操作 = O(N)
    b = b + Math.random()    // $N \times 1$ 操作 = O(N)
}
复制代码

for (let i = 0; i < N/2; i++) {
    b = b + Math.random()    // $ \frac{1}{2} N \times 1$ 操作 = O(N)
}
复制代码

空间复杂度 O(1) 因为不依赖于 N 所以是常数复杂度

for (let i = 0; i < N; i++) {
    for (let j = N; j > i; j--) {
        a = a + i + j;
    }
}
复制代码

最简单有效方法，就是我们将每一个步骤一一列出后来总结规律来解决问题

 i = 0: j = N...1 (N)
 i = 1: j = N...2 (N-1)
 i = 3: j = N...3 (N-2)
 i = N-1: j = N (1)
复制代码

时间复杂度，因为 $O(N^2)$ 复杂度要严格大于 $O(N)$ 的复杂度
$1 + 2 + 3 ,\dots + N = N \times \frac{N + 1}{2} = N \times \frac{N}{2} + \frac{N}{2}$
$= \frac{1}{2} \times O(N^2) + \frac{1}{2} \times O(N) = O((N^2) + O(N) = O((N^2)$

while (i > 0) {
a += i; //1 个操作
i /= 2; //1 个操作
}

在算法中，**时间复杂度**度是一个单位，而不是具体用的时间，这一点希望大家一定要清楚，我们通过不同量级(单位)来衡量单位。例如我们平时使用时间单位，时、分和秒，而不是具体用了几个小时。
 而不是具体给出某一个算法具体耗时。这一点对于初学者可能是比较confusing
###  常数阶 $O(1)$ 

```python
console.log("hello world")
复制代码

这里执行一个操作就是$O(1)$ 一个常数操作，输出三次 HelloWorld 也只算$O(1)$ 这里 1 表示常数单位而不是具体数字 1 的意思。

线性阶$O(n)$

var N = 10;

for(let i = 0; i < N; i++){
    console.log("hello world");
}
复制代码

这里有一个循环说明执行 helloWord 输出操作与 N 有关所以记做$O(N)$

平方阶$O(n^2)$

for(let i =0; i < N; i++){
    for(let j=0; j< N; j++){
        console.log(i)
    }
}
复制代码

立方阶 $O(n^3)$

for(let i =0; i < N; i++){
    for(let n=0; n< N; n++){
        for(let m =0; m < N; m++){
            console.log(i)
        }
    }
}
复制代码

$T(n) = n * n * n = n^3$到现在大家不难发现就是有几层 for 循环，时间复杂度就是 n 的几次方。

对数阶$O(\log n)$

var N = 32
while(N > 0){
  console.log("hello world")
  N = N/2
}
复制代码

这里我们要说一件事，就是这个 $O(\log n)$ 要远远小于 $O(n)$ 只要我们记住$O(1) <$

$O(n \log n) 线性对数阶$

var N = 100
for(let i=1; i<N; i++)
{
    i = 1;
    while(i<N)
    {
        i = i * 2;
    }
}
复制代码

$T(n) = n * \log n$