时间复杂度 Complexity

时间复杂度衡量算法的用时（加法、乘法这样基本操作的数量）随着数据规模的增长而增长的趋势。

最重要的时间复杂度衡量是渐进上界，也就是$f(n)=\mathcal{O}(g(n))$，当且仅当 $\exists c,n_0$，使得 $\forall n \ge n_0,0\le f(n)\le c\cdot g(n)$。

时间复杂度在算法比赛中很重要，因为对于很多问题，正确而巧妙的算法（所谓“正解”）能够在给定的计算时间给出结果（CSP的计算机时间限制一般为1秒）， 而如果没有找到对症下药的正解算法，则往往不能对所有测试例在计算时间限制内给出结果，只能得到部分分数。

资源
OI-Wiki	算法复杂度	时间复杂度和空间复杂度是衡量一个算法效率的重要标准。

一些简单的复杂度例子

• 多层循环

  int n, m;
  std::cin >> n >> m;
  for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
          for (int k = 0; k < m; ++k) {
          std::cout << "hello world\n";
          }
      }
  }

  复杂度是 $\mathcal{O}(n^2 m)$

• DFS：每条边和节点都被访问最多常数次，所以是$\mathcal{O}(n+m)$。

常见算法的复杂度

以下是比赛中一些常用操作的复杂度：

• 没有循环的数学公式运算：$\mathcal{O}(1)$
• 遍历一维数组：$\mathcal{O}(n)$
• 排序(STL sort())：$\mathcal{O}(n\log n)$
• 大部分set/map/priority_queue操作：$\mathcal{O}(\log n)$
• 遍历所有子集：$\mathcal{O}(2^n)$
• 遍历所有排列(STL next_permutation())：$\mathcal{O}(n!)$

题目给出的数据规模往往指明了算法的复杂度上限，很多题目都可以通过数据规模来猜测可能大致用什么类型的算法。这是每道题读题都要快速考虑的步骤。 下表列出常见的数据规模，和对应的算法复杂度上限：

$n$	时间复杂度上限
$n \leq 10$	$\mathcal{O}(n!)$, $\mathcal{O}(n^7)$
$n \leq 20$	$\mathcal{O}(2^n)$, $\mathcal{O}(n^5)$
$n \leq 80$	$\mathcal{O}(n^4)$
$n \leq 400$	$\mathcal{O}(n^3)$,
$n \leq 7500$	$\mathcal{O}(n^2)$
$n \leq 7 \cdot 10^4$	$\mathcal{O}(n\sqrt{n})$
$n \leq 5 \cdot 10^5$	$\mathcal{O}(n \log{n})$
$n \leq 10^7$	$\mathcal{O}(n)$
$n \leq 10^{18}$	$\mathcal{O}(\log^2 n)$, $\mathcal{O}(\log n)$, $\mathcal{O}(1)$