代码之家 › 专栏 › 技术社区 › alcuadrado

计算复杂性练习

big-o complexity-theory

4

alcuadrado · 技术社区 · 17 年前

我正在阅读AHO、Hopcroft和Ullman的“数据结构和算法”,我对练习1.12b感到困惑:

这个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

你能帮帮我吗?

谢谢!

1 回复 | 直到 17 年前

1

6

sharptooth 17 年前

它是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) ^三 )