计算复杂性练习

我正在阅读Aho,Hopcroft和Ullman的"数据结构和算法",我对练习1.12 B感到困惑:

这个Pascal过程的计算复杂度(以Big 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

请你帮助我好吗？

谢谢!

这是O(n ³).big-O显示执行时间(或内存或其他)与任务大小成正比(省略比例系数).

在这种情况下,内部语句的执行次数与(n ³)成比例.我从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 ³).