# Complexity

## 时间复杂度

代码的执行总时间`T(n)`与所有行代码的执行总次数`f(n)`成正比，即：

```
T(n) = O(f(n))
```

n 表示数据规模大小，O 表示正比例函数。

大 O 时间负复杂度并不代表代码真正执行时间，而是表示**代码执行时间随数据规模增长的变化趋势**，也叫**渐进时间复杂度**（asymptotic time complexity），简称**时间复杂度**。

当n很大时，`f(n)`中的低阶、常量、系数并不影响增长趋势，所以可以忽略，如`O(2n^2+2n+3)`可表示为`O(n^2)`。所以时间复杂度分析有一些实用技巧：

1. 只关注循环次数最多的一行代码。
2. 加法法则，总复杂度等于量级最大的复杂度。如，有两段先后执行的代码复杂度分别为`O(n)`与`O(n^2)`，那么总的复杂度为`O(n^2)`。
3. 乘法法则，嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。如，有两段嵌套的代码复杂度分别为`O(n)`与`O(n^2)`，那么总的复杂度为`O(n^3)`。

几种常见的时间复杂度：

```
# 多项式量级
O(1) //常量阶
O(logn) //对数阶
O(n) //线性阶
O(nlogn) //线性对数阶，如归并排序、快速排序
O(n^2) //平方阶
O(n^3) //立方阶
O(n^k) //k次方阶
​
# 非多项式量级
O(2^n) //指数阶
O(n!) //阶乘阶
```

我们把非多项式量级的算法问题称为 **NP 问题**（Non-Deterministic Polynomial）。

当一段代码的复杂度由两个数据规模来决定，并且不知道两个数据规模量级谁的大，那么复杂度对加法规则是： O(f(m) + f(n)) ，乘法规则是：O(f(m) \* f(n)) 。

**不同情况下的复杂度**

* 最好情况时间复杂度（best case time complexity）
* 最坏情况时间复杂度（worst case time complexity）
* 平均情况时间复杂度（average case time complexity）

同一代码块在不同情况下，时间复杂度**有量级差距**，我们就需要使用上述三种复杂度表示。比如下面代码，在数组中查找数据，最好 O(1)，最坏 O(n)，平均 O(n)。

```java
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}
```

**摊还分析**

对一个数据结构进行连续操作，大部分情况时间复杂度很低，只有个别情况时间复杂度很高，而且这些操作之间存在前后关系，这时，可以将这组操作一起分析，看能否把时间复杂度较高的操作平摊到其它时间复杂度较低的操作。摊还分析得到的时间复杂度为**均摊时间复杂度**（amortized time complexity）。

本质上均摊时间复杂度是一种特殊的平均时间复杂度，一般两者相等。

## 空间复杂度

**渐进空间复杂度**（asymptotic space complexity）表示算法的**存储空间与数据规模之间的增长关系**。

常用空间复杂度：`O(1)、O(n)、O(n^2)`。


---

# 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://yunzhao.gitbook.io/notes/computer-science/algorithm/complexity.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.