乐趣区

关于leetcode:搞定大厂算法面试之leetcode精讲2时间空间复杂度

jiezi

搞定大厂算法面试之 leetcode 精讲 2. 工夫空间复杂度

视频教程（高效学习）: 点击学习

目录：

1. 开篇介绍

2. 工夫空间复杂度

3. 动静布局

4. 贪婪

5. 二分查找

6. 深度优先 & 广度优先

7. 双指针

8. 滑动窗口

9. 位运算

10. 递归 & 分治

11 剪枝 & 回溯

12. 堆

13. 枯燥栈

14. 排序算法

15. 链表

16.set&map

17. 栈

18. 队列

19. 数组

20. 字符串

21. 树

22. 字典树

23. 并查集

24. 其余类型题

什么工夫复杂度

工夫复杂度是一个函数，它定性描述该算法的运行工夫，在软件开发中，工夫复杂度就是用来不便开发者估算出程序运行工夫，通常用算法的操作单元数量来代表程序耗费的工夫，这里默认 CPU 的每个单元运行耗费的工夫都是雷同的。假如算法的问题规模为 n，那么操作单元数量便用函数f(n) 来示意，随着数据规模 n 的增大，算法执行工夫的增长率和 f(n) 的增长率出现肯定的关系，这称作为算法的渐近工夫复杂度，简称工夫复杂度，记为 O(f(n))，其中 n 指的是指令集的数目。

什么是大 O

大 O 用来示意算法执行工夫的上界，也能够了解为最差状况下运行的工夫，数据量和程序等状况对算法的执行工夫有十分大的影响，这里假如的是某个输出数据用该算法运行的工夫，比其余数据的运算工夫都要长。

插入排序的工夫复杂度咱们都说是O(n^2)，然而插入排序的工夫复杂度和输出数据有很大的关系，如果输出数据是齐全有序的，则插入排序的工夫复杂度是O(n)，如果输出的数据是齐全倒序的，则工夫复杂度是O(n^2)，所以最坏是O(n^2) 的工夫复杂度，咱们说插入排序的工夫复杂度为O(n^2)。

疾速排序是 O(nlogn)，疾速排序的在最差的状况下工夫复杂度是O(n^2)，个别状况下是O(nlogn)， 所以严格从大 O 的定义来讲，疾速排序的工夫复杂度应该是 O(n^2)，然而咱们仍然说疾速排序的工夫复杂度是O(nlogn)，这是业内默认的规定。

二分查找的工夫复杂度是 O(logn)，每次二分数据规模减半，直到数据规模缩小为 1，最初相当于求 2 的多少次方等于 n，相当于宰割了logn 次。

归并排序的工夫复杂度是O(nlogn)，自顶而下的归并，从数据规模为 n 宰割到 1，工夫复杂度是 O(logn)，而后一直向上归并的工夫复杂度是O(n)，总体工夫复杂度是O(nlogn)。

树的遍历复杂度个别是 O(n)，n 是树的节点个数，抉择排序工夫复杂度是O(n^2)，咱们会在对应的章节逐渐剖析各个数据结构和算法的复杂度。更多的工夫复杂度剖析和推导可参阅主定理。

剖析复杂度的一些规定

  • 多个工夫复杂度相加，如果都是与 n 相干，则取取复杂度高的那一个，例如：O(nlogn + n) = O(nlogn)，O(nlogn + n^2) = O(n^2)。
  • 多个工夫复杂度相加，如果其中有些项的复杂度和 n 不相干则不能疏忽任何项，例如：O(AlogA + B)，O(AlogA + B^2)
  • 两个循环顺次执行，则取复杂度高的那个，嵌套多个循环则须要累乘复杂度。

常见工夫复杂度：

  • O(1): 常数复杂度

    let n = 100;

  • O(logn): 对数复杂度

    // 二分查找非递归
var search = function (nums, target) {
  let left = 0,
    right = nums.length - 1;
  while (left <= right) {let mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) {return mid;} else if (target < nums[mid]) {right = mid - 1;} else {left = mid + 1;}
  }
  return -1;
};

  • O(n): 线性工夫复杂度

    for (let i = 1; i <= n; i++) {console.log(i);
}

  • O(n^2)：平方

    for (let i = 1; i <= n; i++) {for (let j = 1; j <= n; j++) {console.log(i);
  }
}

for (let i = 1; i <= n; i++) {for (let j = 1; j <= 30; j++) {// 嵌套的第二层如果和 n 无关则不是 O(n^2)
    console.log(i);
  }
}

  • O(2^n)：指数复杂度

    for (let i = 1; i <= Math.pow(2, n); i++) {console.log(i);
}

  • O(n!)：阶乘

    for (let i = 1; i <= factorial(n); i++) {console.log(i);
}

常见数据结构根底操作的工夫复杂度

递归的工夫复杂度

递归的工夫复杂度和递归的深度无关

// 递归了 n 层 工夫复杂度 O(n)
function sum2(n) {if (n === 0) {return 0;}
  return n + sum2(n - 1);
}
// 二分查找 递归了 logn 层 O(logn)
var search = function (nums, target) {return search_interval(nums, target, 0, nums.length - 1)
};

function search_interval(nums, target, left, right) {if (left > right) {return -1}
    let mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) {// 判断目标值和两头元素的大小
        return mid
    } else if (nums[mid] < target) {// 递归寻找指标元素
        return search_interval(nums, target, mid + 1, right)
    } else {return search_interval(nums, target, left, mid - 1)
    }
}
// 斐波那契数：递归法求斐波那契数，总共递归了 n 层，二叉树的高度是 n，由咱们的基础知识能够晓得，// 一个高度为 n 的二叉树最多能够有 2^n - 1 个节点，也就是递归过程函数调用的次数，所以工夫复杂度为 O(2^n)。// 咱们能够看到递归树中包涵十分多的反复计算。//0, 1，1，2，3 ...
var fib = function (N) {if (N == 0) return 0;
  if (N == 1) return 1;
  return fib(N - 1) + fib(N - 2);
};

工夫复杂度优化

  • 采纳更好的算法：举例：1+2+3…n 从 1～n 求和，间接循环法，for i->n: sum+=i，咱们也能够用求和公式: n(n+1)/2。在比方有些问题能够用二分查找等。
  • 空间换工夫，工夫是贵重的，咱们计算一个十分耗时的工作，可能要等上很久，忽然的断电，或者意外状况可能会导致十分大的损失，空间是便宜的，最多咱们购买更大内存的服务器，花钱就能够解决，在前面的章节有十分多的这样的例子，比方用 set 或map放慢查找的速度，用二叉搜寻树或者字典树放慢字符串的搜寻。

一个工夫复杂度剖析的例子

有一个字符串数组，将数组中的每个字符串依照字母排序，而后在将整个字符串数组依照字典程序排序。求整个操作的工夫复杂度。

如果我说工夫复杂度是O(n*nlogn + nlogn) = O(n^2logn) 对吗，花工夫思考一下。

咱们来剖析一下，假如最长字符串的长度是 s，数组中有 n 个字符串，对每个字符串排序 O(slogs)，将数组中的每个字符串依照字母排序O(n * slogs)，将整个字符串数组按字典排序 O(s * nlogn)，所以最初的工夫复杂度是O(n * slogs) + O(s * nlogn) = O(nslogs + nslogn) = O(ns * (logs+logn))

空间复杂度

空间复杂度指的是算法在运行过程中所占存储空间的大小，空间复杂度 (Space Complexity) 记作S(n)，仍然应用大 O 来示意。利用程序的空间复杂度，能够对程序运行中须要多少内存有个事后预计。

常见的空间复杂度

  • 一维数组空间，如果存储了 n 个元素，空间复杂度O(n)
  • 二维数组空间，总共有 n 个数组，每个数组存储了 n 个元素，空间复杂度O(n^2)
  • 常数空间复杂度O(1)

递归的空间复杂度

//O(1)
function sum1(n) {
  let ret = 0;
  for (let i = 0; i <= n; i++) {ret += i;}
  return ret;
}

//O(n)，递归了 n 层，递归栈空间是 O(n)的复杂度
function sum2(n) {if (n === 0) {return 0;}
  return n + sum2(n - 1);
}

//O(logn)，递归了 logn 层，递归栈空间是 O(logn)的复杂度
var search = function (nums, target) {return search_interval(nums, target, 0, nums.length - 1)
};

function search_interval(nums, target, left, right) {if (left > right) {return -1}
    let mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) {// 判断目标值和两头元素的大小
        return mid
    } else if (nums[mid] < target) {// 递归寻找指标元素
        return search_interval(nums, target, mid + 1, right)
    } else {return search_interval(nums, target, left, mid - 1)
    }
}
退出移动版