时间复杂度

#OI - 时间复杂度

单循环

eg Code
```
void fun(int n)
{
    int i = 0;
    while (i * i * i <= n)
        i++;
}
```
次数 $0$ 1 2

条件（iii） 0 1 2^3

etc.

规律：当执行至第$k$次时，条件数字即为$k^3$.

设$k^3\leq n$。令$n\rightarrow\infty$，则$k^3=n$.

则$k=\sqrt[3]{n}$.此算法的时间复杂度即为$O(\sqrt{n})$.（略去了常数因子）

例2
```
void fun(int n)
{
    int i = 1;
    while (i <= n)
        i *= 2;
}
```
次数 $0$ 1 2

条件（i） 1 2 2^2

规律：同上，$2^k=n$，$k=\log_2n$.

$\therefore O(\log n)$.

例3
```
void fun(int n)
{
    int x = 0;
    while (n >= (x + 1) * (x + 1))
        x += 1;
}
```
条件为$(x+1)^2$，同样列表可知$(k+1)^2=n$，$k=\sqrt{n}-1$.

在时间复杂度中，常数项一般略去。

$\therefore O(\sqrt{n})$.
多层循环

情况1 - 外层不影响内层
```
void fun(int n)
{
    int count = 0;
    for (int k = 1; k <= n; k *= 2)
        for (int j = 1; j <= n; j++)
            count++;
}
```
可看作是两个单循环。

先计算外循环。同理列表，

次数 0 1 2

条件 1 2 4

故$2^k=n$，$k=\log_2n$.

内循环同理列表，$O(n)$.

整体算法的时间复杂度为内外循环相乘，$n\log_2n$.

此处注意，由于换底公式，$\log_an$与$\log_bn$仅有一个因子不同，故在计算时间复杂度时不论对数的底。

算法的时间复杂度为$O(n\log n)$.

情况2 - 外层影响内层

即内层的条件与外层有关。
```
void fun(int n)
{
    int m = 0, i, j;
    for (i = 1; i <= n; i++)
        for (int j = 1; j <= i * 2; j++)
            m++;
}
```
首先介绍一些公式：

$$ \sum_{i=1}^ni=\frac{n(n+1)}{2}$$ $$ \sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}{6} $$

特殊地，对于常数列求和：

$$ \sum_{i=1}^nk=kn $$

那么对于此题，可知：

外层循环的循环次数为$\sum_{i=1}^n$，内层为$\sum_{j=1}^{2i}1$。

两式相乘，得到

$$ \sum_{i=1}^n\sum_{j=1}^{2i}1=\sum_{i=1}^n2i $$$$ 由公式1，原式=\frac{n(n+1)}{2} $$

故总共执行$\frac{n^2+n}{2}$次。时间复杂度$O(n^2)$.（取最高次）

次数	$0$	1	2
条件（iii）	0	1	2^3

次数	$0$	1	2
条件（i）	1	2	2^2

次数	0	1	2
条件	1	2	4

在计算好语句块的执行次数后，需要注意在整理成时间复杂度时略去常数因子，如$\log_2n$的底、$\sqrt[3]n$的根指数等，写成$O(\log n)$、$O(\sqrt n)$.