math - The running time of my program in big O time

Question

Can someone help me figure out the running time of this loop? I believe it is O(5nlogn).

for(int f = 0; f < Array.length; f++) {
    F = Array[f];
    for(int e = 0; e <= f; e++) {
        E = Array[e];
        for(int d = 0; d <= e; d++) {
            D = Array[d];
            for(int c = 0; c <= d; c++) {
                C = Array[c];
                for(int b = 0; b <= c; b++) {
                    B = Array[b];
                    for(int a = 0; a <= b; a++) {
                        A = Array[a];
                    }
                }
            }
        }
    }
}

Thanks

Answer 1

答案是Θ(n ⁶ )。n我写了一个程序来模拟内循环并记录一系列执行发生了多少次：

static void Main(string[] args)
{
    int arrLength = 20;
    int[] arr = new int[arrLength];

    for (int f = 0; f < arrLength; f++)
    {
        for (int e = 0; e <= f; e++)
        {
            for (int d = 0; d <= e; d++)
            {
                for (int c = 0; c <= d; c++)
                {
                    for (int b = 0; b <= c; b++)
                    {
                        //for (int a = 0; a <= b; a++)
                        arr[b] = arr[b] + 1;
                    }
                }
            }
        }
    }

    for (int i = 0; i < arr.Length; i++)
    {
        Debug.WriteLine(string.Format("{0} execution: {1} time(s).", i + 1, arr[i]));
        Console.WriteLine(string.Format("{0} execution: {1} time(s).", i + 1, arr[i]));
    }

    Console.ReadLine();
}

以 1 的 arrLength 运行它会给出：

1 execution: 1 time(s).

以 2 的 arrLength 运行它会给出：

1 execution: 5 time(s).
2 execution: 1 time(s).

以 3 的 arrLength 运行它会给出：

1 execution: 15 time(s).
2 execution: 5 time(s).
3 execution: 1 time(s).

事实证明，执行时间总是遵循相同的等式。在 arrLength 为 20 时，我们得到：

1 execution: 8855 time(s).
2 execution: 7315 time(s).
3 execution: 5985 time(s).
4 execution: 4845 time(s).
5 execution: 3876 time(s).
6 execution: 3060 time(s).
7 execution: 2380 time(s).
8 execution: 1820 time(s).
9 execution: 1365 time(s).
10 execution: 1001 time(s).
11 execution: 715 time(s).
12 execution: 495 time(s).
13 execution: 330 time(s).
14 execution: 210 time(s).
15 execution: 126 time(s).
16 execution: 70 time(s).
17 execution: 35 time(s).
18 execution: 15 time(s).
19 execution: 5 time(s).
20 execution: 1 time(s).

将其插入令人敬畏的整数序列在线百科全书，我们得到二项式系数 binomial(n,4)，它是这样的（序列从偏移量 4 开始）：

binomial(n,4)
n*(n-1)*(n-2)*(n-3)/24
0 = 0
1 = 0
2 = 0
3 = 0
4 = 1
5 = 5
6 = 15
7 = 35
...

如果我们查看上面我的程序输出的执行模式，我们可以使用求和和这个二项式序列来重写它。对于介于 1 和 n 之间的每个整数 i，我们将序列(n - i + 4)th中的数字binomial(n,4)乘以i，作为执行的总数。这表示如下：

代入j = n - i + 1，并意识到j从 n 到 1，我们可以将这个等式重写为：

依靠Wolfram Alpha来计算这个方程，我插入sum (n-j+1)(j+3)(j+2)(j+1)*j/24, j = 1 to n，它想出了：

这很明显是 Θ(n ⁶ )，所以这就是我们的答案。

最终方程实际上是binomial(n,6)，所以对于 m 个循环，最内层循环的执行次数可能是binomial(n,m)。对于给定数量的 m 个循环，我们有：

Answer 2

做到这一点的一个好方法是考虑您正在迭代的空间。如果您考虑一下，循环将迭代 (a, b, c, d, e, f) 的非负整数值，其中

n > f ≥ e ≥ d ≥ c ≥ b ≥ a

这些迭代中的每一个都做 O(1) 工作（所有循环只分配一个变量，这需要 O(1) 工作），所以问题是有多少可能的值满足上述公式。我将声称它是Θ(n ⁶ )，并将尝试用我的其余答案来证明这一点。

首先，请注意该值肯定不会超过 O(n ⁶ )。所有 a、b、c、d、e 和 f 的范围都在 0 和 n-1 之间，因此每个最多有 n 个不同的值。因此，它们可以具有的最大可能值数是 n ⁶。这不是一个严格的界限，但它肯定是一个上限。这让我们知道运行时间最多为 O(n ⁶ )。

如果我们想获得更紧密的界限，我们必须更加努力。为此，我将使用以下事实：

1 ^k + 2 ^k + 3 ^k + ... + n ^k = Θ(n ^k )

这是一个几何级数的总和，这就是它的来源。

这意味着

sum(f from 0 to n-1)
   sum (e from 0 to f)
      sum (d from 0 to e)
          sum (c from 0 to d)
              sum (b from 0 to c)
                  sum (a from 0 to b)
                      1

=  sum(f from 0 to n-1)
     sum (e from 0 to f)
        sum (d from 0 to e)
            sum (c from 0 to d)
                sum (b from 0 to c)
                    Theta(b)

=  sum(f from 0 to n-1)
     sum (e from 0 to f)
        sum (d from 0 to e)
            sum (c from 0 to d)
                Theta(c^2)

=  sum(f from 0 to n-1)
     sum (e from 0 to f)
        sum (d from 0 to e)
            Theta(d^3)

=  sum(f from 0 to n-1)
     sum (e from 0 to f)
        Theta(e^4)

=  sum(f from 0 to n-1)
     Theta(f^5)

= Theta(n^6)

希望这可以帮助！