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

计算复杂性练习

  •  4
  • alcuadrado  · 技术社区  · 16 年前

    我正在阅读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 回复  |  直到 16 年前
        1
  •  6
  •   sharptooth    16 年前

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