time - 以下算法的 bigOh 或运行时间是多少

Question

以下算法在 bigO 中的运行时间是多少？

for(int i=1;i<=n;i++){
    for(int j=i;j<=n;j++){
        for(int k=j; k<=n;k++){
            for(int l=k; l<=n;l++){

                ...

            }
        }
    }
}

score 7 · Accepted Answer

7

这个算法似乎是n^4。当然，从理论角度来看（没有任何编译器考虑）。

于 2013-01-10T20:12:51.610 回答

score 2 · Accepted Answer

2

N^4。小数部分不算。

于 2013-01-10T20:13:27.397 回答

score 1 · Accepted Answer

这种依赖循环集合的公式可以推断如下：

在此处输入图像描述

其中c（常数）是最内层循环内的操作数，n是元素数，r是嵌套循环数。

在问题的情况下：

在此处输入图像描述

另一种有效但乏味的方法是使用 Sigma 表示法：

在此处输入图像描述

score 0 · Accepted Answer

O(N^4) 是成本。

每个嵌套都是 N^ 所以本质上是 N * N * N * N = N^4

CS610，算法开发，新泽西理工学院。我的研究生课程实际上派上用场了。

score 0 · Accepted Answer

我的答案是 O(N^4)……因为有四个“for 循环”……而且很容易判断这个算法的运行时间……谢谢！

time - 以下算法的 bigOh 或运行时间是多少

5 回答 5

Related

Reference