算法     +      数据结构      =   程序

Algorithms + Data Structures = Program

算法要满足的5个重要特性

  • 有穷性
  • 确定性
  • 可行性
  • 输入
  • 输出

评价算法优劣的基本标准

  • 正确性
  • 可读性
  • 健壮性
  • 高效性

时间复杂度

也称渐近时间复杂度，T(n)=O(f(n))，随着问题规模 n的增大，算法执行时间和增长率和f(n)增长率成正比。
对算法时间复杂度的度量，通常只讨论算法在最坏情况下的时间复杂度即分析在最坏情况下，算法执行时间的上界。

如何计算时间复杂度

常量阶示例

1
2
x++;		//频度为1
s =  0; 	//频度为1

$$
f(n) = 1+1=2
$$
及
$$T(n) =O(1)$$

1
2
3
4
for(int i=1;i<=10000;i++){
    x++;
    s = 0;
}

虽然上述代码循环了1w次，但还是属于常数阶，所以：
$$T(n) =O(1)$$

实际上，如果算法执行时间不随着n的规模的增长而增长，那么算法当中语句的频度就是某个常数，即使常数再大，算法的时间复杂度都为 O(1)

线性阶示例

1
2
3
4
for(int i=1;i<=n;i++){  //频度为n+1
    x++;                //频度为n
    s = 0;              //频度为n
}

$$ f(n)=(n+1)+n+n=3n+1 $$
及
$$ T(n)=O(n) $$

平方阶示例

1
2
3
4
5
6
7
8
9
10
x = 0;  //频度为1
y = 0;  //频度为1
for(int k=1;k<=n;k++){      //频度为n+1
    x++;                    //频度为n
}
for(int i=1;i<=n;k++){      //频度为n+1
    for(int j=1;j<=n;k++){  //频度为n*(n+1)
        y++;                //频度为n^2
    }
}

$$ f(n)=1+1+(n+1)+n+(n+1)+n(n+1)+n^2=2n^2+4n+4 $$
及
$$ T(n)=O(n^2) $$

对数阶示例

1
2
3
4
for(int i=1;i<=n;i=i*2){
    x++;
    s = 0;
}

我们可以通过画表得到：

次数 1 2 3 4 t
i 1 2 4 8 ?
i $ 2^0$ $ 2^1$ $ 2^2$ $ 2^3$ $ 2^{t - 1} $

易得
$$
\begin{align}
2^{t - 1} &> n \notag\
\log_2{2^{t - 1}} &> \log_2{n} \notag\
t - 1 &> \log_2{n} \notag
\end{align}
$$
及
$$
\begin{equation}
\begin{split}
T(n)&=\log_2{n}+1 \notag\
&=O(\log_2{n}) \notag
\end{split}
\end{equation}
$$

时间复杂度汇总

时间 名称
$1$ 常数阶
$n$ 线性阶
$n^2$ 平方阶
$n^3$ 立方阶
$\log n$ 对数阶
$n\log n$ 线性对数阶
$2^n$ 指数阶
$n!$ 阶乘阶