点击查看【bilibili】

时间复杂度

时间复杂度为O(1)的例子

if(i==1)
a=1     result =3+4     result =n*2    result=10000* 10000
array.push('a')   array.pop()
map.set(1,1)      map.get(1,1)

在计算复杂度的时候，O(1)一般会被忽略。但也有时间复杂度为O(1)的题

时间复杂度为O(n)的例子

for循环, while循环.(不使用二分搜索)
for(let i=O;i<n;i++)    let i=O; while(i<n)

let a = O;
for(let i=O;i<n;i++){
    a+=i;
}

时间复杂度为O(n2)的例子

嵌套for循环,嵌套while循环.
for(let i=0;i<n;i++){
    for(let j=0;j<n;j++){
        a+=i;
    }
}

时间复杂度为O(n)而非O(n2)
for(let i=0;i<n;i++){
}

for(let j=0;j<n;j++){
    a+=i;
}

时间复杂度为O(n)而非O(n2)
while(i<n){
    i++; j=i;
  while(j<n){
        i++;
    }
}

复杂度的计算

取复杂度最高的一项作为总体复杂度，前面的常数忽略

1. n +n+1时间复杂度是n
2. 2n+ 3n+ 6时间复杂度是n

   时间复杂度优化实例

   https://leetcode-cn.com/problems/two-sum/

   时间复杂度为O(log n)和O(n log n)

• Log n - 二分搜索
  • https://leetcode-cn.com/problems/binary-search/

• N log n - 排序

  • array.sort()

    时间复杂度为O(n), O(2^n), O(n!)

• o(n);: https://leetcode-cn.com/problems/4sum/

• o(2^n): https://leetcode-cn.com/problems/fbonacci-number/

• 高于O(n)的，很多都属于需要优化的算法

  优化的方法:从低一级的复杂度寻找灵感

  o(n)->O(log n) 使用二分搜索
  o(n log n)->O(n) 遇到需要排序的题，想想能否通过数组,set, map,heap解
  o(n)->O(n log n) 遇到嵌套循环，想想能不能通过排序 + 一个for循环解
  https://leetcode-cn.com/problems/valid-anagram/
  https://leetcode.com/problems/merge-intervals

  空间复杂度

  空间复杂度为O(1)的例子

  const a = 1
  let a ='a'
  

  与时间复杂度不同，有很多题的空间复杂度就是O(1)

  空间复杂度为O(n)的例子

• 定义一个长度为n的数组

• 定义一个长度为n的set, map

• 用for循环生成一个长度为n的链表

  空间复杂度为O(n2)的例子

• 二维数组

• 一维数组每个元素存放一个长度为n的set或者map或者链表

  时间复杂度与空间复杂度的取舍

• 一般是取时间复杂度较低的方法

https://leetcode-cn.com/problems/two-sum/

• 强制要求选择哪个复杂度

https://leetcode-cn.com/problems/set-matrix-zeroes/