complexity-theory - 计算复杂度练习

Question

我正在阅读 Aho、Hopcroft 和 Ullman 的“数据结构和算法”，我对练习 1.12 B 感到困惑：

这个 Pascal 过程的计算复杂度（用大 O 表示法表示）是多少？

procedure mysterious( n: integer );
    var
        i, j, k: integer;
    begin
        for i := 1 to n - 1 do
             for j := i + 1 to n do
                 for k := 1 to j do
                    {mysterious statement of O(1)}
    end

请你帮助我好吗？

谢谢！

Answer 1

它是 O(n ³ )。big-O 显示执行时间（或内存或其他）如何与任务的大小成比例（省略比例系数）。

^{在这种情况下，内部语句的执行次数与 (n 3} )成正比。i 从 1 运行到 (n-1) - 因此外循环内的所有内容都执行 (n-1) 次。j 平均从 (n/2) 到 (n) 运行 - 所以里面的所有东西都被执行 (n-1)* (n/2) 次。k 平均从 1 运行到 (3/4* n)。这将获得 (n-1)* (n/2)* (3/4*n-1) 内部语句的执行。这是 O(n ³ )。