2020 算法时间复杂度和空间复杂度(补)

algorithms_rogramming.jpg

今天我们继续把时间复杂度这件来说清楚，在今天硬件条件下我们更重视时间复杂度，所以有人提到用空间来换时间，毕竟时间是宝贵的。在算法中，时间复杂度度是一个单位，而不是具体用的时间，这一点希望大家一定要清楚，我们通过不同量级(单位)来衡量单位。例如我们平时使用时间单位，时、分和秒，而不是具体用了几个小时。
而不是具体给出某一个算法具体耗时。这一点对于初学者可能是比较confusing

常数阶 $O(1)$

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$

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

2020 算法时间复杂度和空间复杂度(补)