本节课主要内容

常用网站

意义在于我们在处理计算问题时候能够通过 科学方式 分析该问题，意味着我们能够建立数学的模型。

通过模型可以：

程序的运行时间可以简单认为与两点有关：

很明显，执行每条语句的耗时会受具体环境的影响，比如 1GHZ 和 10 GHZ。

而在实际分析算法性能时，我们期望建立统一的模型。因此也就引入了渐进复杂度分析。通常我们使用「大O符号表示法」，表示渐进增长的上限。另外其他的渐进表示符号大家随便找本教材看下就好了。

举个例子：

function  sum(n) {
    let sum = 0;
    for(let i = 0; i <= n; i++) {
        sum += i;
    }
}

那么该算法的时间复杂度就是 $T(n) = O(f(n)) = O(n)$, 这里 f(n) 表示每行代码执行的次数之和。那么实际上我们执行了多少行代码呢？

所以 $f(n) = 3*n + 6$ 。上面说了大 O 表示的是渐进增长的趋势，所以可以去掉所有的常系数和低阶的影响因子。所以也就是 $O(f(n)) = O(n)$

常见的时间复杂度如下所示：

在实际算法练习中，比较有用的是，可以从数据范围大概推算出支持的时间复杂度和对应可能的算法：一般来讲，笔试题或竞赛中时间限制是1秒或2- 秒（单 test case）。在这种情况下，C++代码中的操作次数控制在 $10^7$ 为最佳（1 GHZ）。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择( YXC 总结)：

$n≤30$ => $O(2^n)$：dfs + 剪枝，状态压缩 dp
$n≤100$ => $O(n^3)$: 图论中的 floyd，部分 dp
$n≤1000$ => $O(n^2)$ / $O(n^2logn)$: dp，二分，图论中的朴素版 Dijkstra、朴素版 Prim、Bellman-Ford
$n≤10^4$ => $O(n*\sqrt(n))$: 块状链表、分块、莫队
$n≤10^5$ => $O(nlogn)$: 各种sort，线段树、树状数组、set/map(红黑树)、heap、拓扑排序、dijkstra（heap 优化）、prim（heap 优化）、spfa、求凸包、求半平面交、二分
$n≤10^6$ => $O(n)$ / 常数较小的 $O(nlogn)$ 算法 :
- hash、双指针扫描、并查集，kmp、AC自动机
- 常数比较小的 $O(nlogn)$：sort、树状数组、heap、dijkstra(heap 优化)、spfa
$n≤10^7$ => $O(n)$: 双指针扫描、kmp、AC自动机、线性筛素数
$n≤10^9$ => $O(\sqrt(n))$: 判断质数
$n≤10^{18}$ => $O(logn)$: 最大公约数，快速幂
$n≤10^{1000}$ => $O((logn)^2)$，高精度加减乘除