11-30 07:47 阅读 242

时间复杂度和空间复杂度(算法的时间复杂度和空间复杂度)

时间复杂度和空间复杂度

出现原因：不受外在因素影响的、大致的估计算法执行效率的方法

从算法所占用的「时间」和「空间」两个维度去考量。

时间复杂度：代码执行时间随数据规模增长的变化趋势**，并不是代码执行的具体时间。
空间复杂度：算法的存储空间与数据规模之间的增长关系。
通常都是用「 大O符号表示法 」，即 T(n) = O(f(n))
f(n) 表示每行代码执行次数之和
O 表示正比例关系
n：表示数据规模的大小

时间复杂度

function fun1(n) {
  let sum = 0, i = 0;
  for (; i <= n; i++) {
    sum += i
  }
  return sum
}
function fun2(n) {
  let sum = 0, sum1 = 0, i = 0, j = 0;
  for (; i <= n; i++) { // 循环1
    sum += i
  }
  for (i = 0; i <= n; i++) { // 循环2
    for (j = 0; j <= n; j++) {
      sum += i * j
    }
  }
  return sum
}
function fun3(n) {
  let sum = 0, i = 0;
  for (; i <= n; i++) {
    sum += fun(i)
  }
  return sum
}复制代码

fun1 中第1行都是常量，对 n 的影响不大，所以总的时间复杂度要看第2、3行的循环，即时间复杂度为： O(n)

fun2 中循环1的时间复杂度为 O(n) ，循环2的时间复杂度为 O(n²)，当 n 趋于无穷大时，总体的时间复杂度要趋于 O(n²) ，即上面代码的时间复杂度是 O(n²)

fun3 的时间复杂度是 O(n * T(fun)) = O(n*n) ，即 O(n²)

所以：T(c+n)=O(n)，T(m+n)=O(max(m, n))，T(n) = T1(n) T2(m) = O(nm)，其中 c 为常量

常见复杂度（按数量阶递增）

常量阶O(1)

当算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)

let i = 2
let j = 3
++j
i++
let sum = i+j复制代码

对数阶O(logn)

let i=1;
while (i <= n)  {
  i = i * 2
}复制代码

每次循环都是i乘上2, 执行过程也是： 2, 2², 2³..., 2^x, n,在循环了x次后，i > n,循环结束，总执行了x次，即是： 2^x = n, 可以推出 x = O(log₂n)，时间复杂度为O(logn)

线性阶O(n)

一般在循环中出现较多

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

上述代码循环执行n遍，消耗时间随n变化而发生变化，时间复杂度为O(n)

线性对数阶O(nlogn)

简单理解为有个循环n遍的代码，内层代码的时间复杂度为O(logn)，总体复杂度就是O(nlogn)

例子

for(let k=1; k < n; k++){
    i = 1;
    while(i<n){
        i = i * 2;
    }
}复制代码

平方阶O(n²)

一般多指双层循环，O(n)里面嵌套有一个O(n),最后时间复杂度就是O(n²)

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

立方阶O(n³)

相当于三层n循环

K次方阶O(n^k)

相当于k层n循环

空间复杂度

空间复杂度 O(1)

执行代码所需要的空间消耗不会随某个变量n发生变化，而是恒定的，可表示为 O(1)

let i = 2
let j = 3
++j
i++
let sum = i+j复制代码

空间复杂度 O(n)

let arr = [];
for (let i = 0; i < n; i++) {
  arr.push(i)
}复制代码

第一行声明了个数组，此时空间消耗为1，第2-6行，是一个循环体，每次循环就往数组新增一个变量，消耗的存储空间为n，执行整段代码所需的存储空间为O(1+n), 空间复杂度为O(n)

作者：LastStarDust
链接：https://juejin.cn/post/7036272356456661022

伪原创工具 SEO网站优化 https://www.237it.com/