# 大O表示法

大O表示法全称大 O 时间复杂度表示法，表示代码执行时间随数据规模增长的变化趋势。大O表示法用于粗略地估计算法的执行效率，所以大O表示法只关注量级最大的那段代码（**一般就是循环执行次数最多的那段代码**）

## 时间复杂度

### O(1)

代码中不存在循环语句、递归语句，即时千行万行，复杂度也是 O(1) 

### O(n)

代码中存在循环语句、递归语句

```javascript
const print = n => {
  for (let i = 0; i< n; i++) {
    console.log(i)
  }
}
```

该方法中， `print` 方法中 `for` 循环执行了 `n` 次，所以时间复杂度是 O(n)&#x20;

### O(logn)

循环退出条件不是线性增加的

```javascript
const print = n => {
 let i = 1
 while (i <= n)  {
   i = i * 2
   console.log(i)
 }
}
```

代码中循环条件变量 `i` 每循环一次就乘以 2 ，当 `i` 大于 2 时循环结束。因此循环次数为

```
2^0 * 2^1 * 2^2 * 2^3 * .... 2^x = n
```

因此`x = log2n` ，大O简写为 O(logn)

### O(m\*n) O(m+n)

如果代码中有两个循环，分别循环了 `m` 次和 `n` 次。如果这两个循环存在嵌套关系，则其复杂度为 `O(m*n)` ，如果不存在嵌套关系，则其复杂度为 `O(m+n)`

## 空间复杂度

**空间复杂度 O(1)**

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)\
举例：

```javascript
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
```

代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

**空间复杂度 O(n)**

```
int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}
```

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)