Skip to content

复杂度 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)\)