我将如何在 Big Theta Θ 表示法下分析该算法的形式复杂性？

Question

我需要一些帮助来理解使用 Big Theta Θ 符号的算法分析：

Big O is the most commonly used asymptotic notation for comparing functions, although in many cases Big O may be replaced with Big Theta Θ for asymptotically tighter bounds.

我将如何逐步分析这个算法？我知道最终答案是 ϴ(n²)，但我看不懂。任何帮助将不胜感激。

为简单起见，您可以假设 n = 2k，对于某个正整数 k.

 int a = 0;
 int i = n * n;
 while (i > 0) {
      for (int j = 0; j < i; j++) {
          a++; 
      }
      i = i/2;
 }

Answer 1

基本上，外循环控制i的值。每次循环通过时，i 除以二。循环的初始值为 i、i/2、i/4...

内循环包含 i 计算。如果你总结这个，你会得到 i + i/2 + i/4 + i/8 + i/16 + ... <= 2 * i。（<= 因为我们使用整数除法，它总是 <= 真实值）

所以总计算次数<= i == 2 * n * n.

我们也可以看到计算次数>= i = n*n。由于它上下以 n*n 和 2*n*n 为界，因此它是 Big Theta(n^2)

Answer 2

 int a = 0, i=n*n;
 while(i > 0)
 {
      for(int j=0; j<i; j++)
         { a++; }
      i=i/2;
 }

你执行了多少次for循环：

第一次通过 while 循环，i = n^2

第二次，i/2 = (n2)/2

第三，(n2)/4

因此将它们相加得到 n^2 + n^2/2 + n^2/4 + ....

倾向于 2n^2 = O(n^2) 因为大 O 表示法只关心 n

的顺序

Answer 3

计算 a 递增的次数：

n^2 on the first iteration
+
n^2 / 2 on the second iteration
+
...
+
n^2 / 2^k on the (k+1)-th iteration

我们有 k = log(n^2) = 2*log(n)，因为我们在每一步除以 2。

所以我们得到了第一项 n^2、比率 1/2 和 2*log(n) 项的几何级数之和，或者为了使事情更简单，第一项 1和比率 2:

S = O(2^(2*log(n))) = O([2^log(n)]^2) = O(n^2)

=> The entire algorithm is BigTheta(n^2)

Answer 4

让我们暂时忽略 i = n * n 这个事实，只考虑算法

while(i > 0)
{
    for(int j=0; j<i; j++)
       { a++; }
    i=i/2;
}

i = i/2 表示 i 除以 2，向下舍入。在最坏的情况下，将不会进行四舍五入。如果 i 是 2 的幂，就会发生这种情况。让我们假设 i == 16。 i 的值则为 16, 8, 4, 2, 1。 for 循环有 i 次迭代，因此执行的总次数 a++; 为 16 + 8 + 4 + 2 + 1 = 31。一般来说，如果 i 是 2 的幂，a++; 会发生 2i - 1 次。因此，从渐近的角度来看，复杂度在 i 或 O(i) 中是线性的。

自i == n^2以来，复杂度为O(n^2)。

为了证明它是 Theta(n^2) 我们必须证明运行时间总是大于 n^2 的固定倍数。但是在这种情况下我们可以看到 a++ 发生的次数超过了 n^2 的 1 次，因为 n^2 是 i.

的第一个值

我将如何在 Big Theta Θ 表示法下分析该算法的形式复杂性？

How would I go about analyzing the formal complexity of this algorithm under Big Theta Θ notation?

java

algorithm

complexity-theory