复杂度 Complexity

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

时间复杂度

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

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

一些简单的复杂度例子

• 多层循环

  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";
      }
  }
  }
  

  复杂度是\(O(n^2 m)\)

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