# 大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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mm.ricky.moe/algorithm/algorithm-and-data-structure/ji-chu-zhi-shi/daobiao-shi-fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.