一、基本概念

1、时间复杂度

image.png
1、O(1)
一次就够

  1. function fn(obj={}){
  2.   return obj.a + obj.b + obj.c  //4~5 
  3. }

2、O(n)
和传输的数据量一样

  1. function fn(arr=[]){
  2.   for(let i=0;i<arr.length;i++){
  3.     console.log(arr[i])
  4.   }
  5. }

3、O(n^2)
数据量的平方

  1. function fn(arr=[]){
  2.   for(let i=0; i<arr.length; i++){
  3.     for(let j=0; j<arr.length; j++){
  4.       console.log(arr[j])
  5.     }
  6.   }
  7. }

4、O(logn)
数据量的对数

  1. function fn(arr){
  2.   //二分查找、有序数组
  3. }

5、O(nlogn)
数据量 * 数据量的对数

  1. function fn(arr=[]){
  2.   for(let i=0;i<arr.length;i++){
  3.     //二分
  4.   }
  5. }

2、空间复杂度

1、O(1)
一次就够

  1. function fn(){
  2.   const arr1 = []
  3.   const arr2 = []
  4. }

2、O(n)
和传输的数据量一样

  1. function fn(arr=[]){
  2.   const arr2 = []
  3.   for(let i=0; i<arr.length; i++){
  4.     arr2[i] = arr[i] + 10
  5.   }
  6.   return arr2
  7. }

3、O(n^2)
数据量的平方

4、O(logn)
数据量的对数

5、O(nlogn)
数据量 * 数据量的对数

3、js操作的时间复杂度

前端重时间，轻空间

（1）高时间复杂度
unshift shift splice
数组是一个有序结构，unshift 操作非常慢！！！ O(n)

（2）低时间复杂度
pop push slice 原数组没被改变

4、二叉查找树

每一个节点都可能有任意个数的子节点（在二叉树中我们称之为度，2 个子节点就是 2 度）
当某个节点拥有 0 个子节点时，我们称之为叶子节点或终端节点。
每一个节点的左子节点的数值要小于当前节点，每一个节点的右子节点要大于当前节点

image.png

5、平衡二叉树

二、算法题

1、将一个数组旋转k步

思路1：
将 k 后面的元素，挨个 pop 然后 unshift 到数组前面
复杂度：
时间复杂度：O(n^2)
空间复杂度：O(1)

  1. function rotate1(arr: number[], k: number): number[] {
  2.   const length = arr.length
  3.   if (!k || length === 0) return arr
  4.   const step = Math.abs(k % length) // abs 取绝对值
  6.   // O(n^2)
  7.   for (let i = 0; i < step; i++) {
  8.     const n = arr.pop()
  9.     if (n != null) {
  10.       arr.unshift(n) // 数组是一个有序结构，unshift 操作非常慢！！！ O(n)
  11.     }
  12.   }
  13.   return arr
  14. }

思路2：

  • 将 k 后面的所有元素拿出来作为 part1
  • 将 k 前面的所有元素拿出来作为 part2
  • 返回 part1.concat(part2)

复杂度：
时间复杂度：O(1)
空间复杂度：O(n)

  1. function rotate2(arr: number[], k: number): number[] {
  2.   const length = arr.length
  3.   if (!k || length === 0) return arr
  4.   const step = Math.abs(k % length) // abs 取绝对值
  6.   // O(1)
  7.   const part1 = arr.slice(-step) // O(1)
  8.   const part2 = arr.slice(0, length - step)
  9.   const part3 = part1.concat(part2)
  10.   return part3
  11. }

测试用例
npx jest ./src/01-algorithm/array-rotate.test.ts

  1. /**
  2.  * @description Array rotate test
  3.  * @author cq
  4.  */
  6. import { rotate1, rotate2 } from './array-rotate'
  8. describe('数组旋转', () => {
  9.     it('正常情况', () => {
  10.         const arr = [1, 2, 3, 4, 5, 6, 7]
  11.         const k = 3
  13.         const res = rotate2(arr, k)
  14.         expect(res).toEqual([5, 6, 7, 1, 2, 3, 4]) // 断言
  15.     })
  17.     it('数组为空', () => {
  18.         const res = rotate2([], 3)
  19.         expect(res).toEqual([]) // 断言
  20.     })
  22.     it('k 是负值', () => {
  23.         const arr = [1, 2, 3, 4, 5, 6, 7]
  24.         const k = -3
  26.         const res = rotate2(arr, k)
  27.         expect(res).toEqual([5, 6, 7, 1, 2, 3, 4]) // 断言
  28.     })
  30.     it('k 是 0',  () => {
  31.         const arr = [1, 2, 3, 4, 5, 6, 7]
  32.         const k = 0
  34.         const res = rotate2(arr, k)
  35.         expect(res).toEqual(arr) // 断言
  36.     })
  38.     it('k 不是数字', () => {
  39.         const arr = [1, 2, 3, 4, 5, 6, 7]
  40.         const k = 'abc'
  42.         // @ts-ignore
  43.         const res = rotate2(arr, k)
  44.         expect(res).toEqual(arr) // 断言
  45.     })
  46. })

性能测试

  1. const arr1 = []
  2. for (let i = 0; i < 10 * 10000; i++) {
  3.     arr1.push(i)
  4. }
  5. console.time('rotate1')
  6. rotate1(arr1, 9 * 10000)
  7. console.timeEnd('rotate1') // 885ms O(n^2)
  9. const arr2 = []
  10. for (let i = 0; i < 10 * 10000; i++) {
  11.     arr2.push(i)
  12. }
  13. console.time('rotate2')
  14. rotate2(arr2, 9 * 10000)
  15. console.timeEnd('rotate2') // 1ms O(1)

思路1 pop unshift
image.png
思路2 拆分两个数组，concat连接
image.png