Big-theta边界，算法分析

Question

我正在努力学习如何找到各种算法的big-theta界限，但我很难理解如何做到这一点，即使在阅读了这里的一些问题和关于这个主题的讲座和教科书之后。举个例子

procedure for array a{
    step=1
    while(step <= n){
      i = n
      while(i >= step){
        a[i]= a[i-step] + a[i]
        i = i - 1}
      step = step * 2}
    }

我想通过n来计算加法次数的大θ界限，n是数组a中的索引数量。我可以看到外部循环本身经历了log(n)次迭代，但我不知道如何表达内部循环中发生的事情。有没有人可以给我一个解释，或者甚至是一个我可以尝试咨询的资源？

Answer 1

Big Theta notation要求我们找到两个常数，k1和k2，使得我们的函数f( n )在足够大的n时在k1*g(n)和k2*g(n)之间。换句话说，我们是否可以找到一些其他函数g(n)，它在某个点小于f(n)，在另一个点大于f(n) (单调)。

为了证明Big-Theta，我们需要找到g(n)，使得f(n)是O(g(n)) (上界)，f(n)是Big-Omega(g(n)) (下界)。

证明大O

根据log大O对数表示法(其中f( n ) log(n) *k)，您的算法f(n)是O((N)*n)，在本例中g(n) = <= (N)*n。

让我们证明这一点：

查找内循环执行

外部循环执行了多少次？跟踪"step“变量:假设n是100：

• 1
• 2
• 4
• 8
• 16
• 32
• 64
• 128 (不执行此循环)

对于100的输入值，这是7次执行。我们可以等价地说，它执行对数次数(实际上是(log n) (Log)次，但log(n)就足够了)。

现在让我们看一下内部循环。跟踪i变量，该变量从n开始递减，直到每次迭代的大小为step。因此，对于每个step的值，内部while循环将执行n步次数。

例如，当n = 100

代码100-1= 99 iterations

• 100 -2= 98 iterations

• 100 -4= 96次迭代

• 100 -8= 92次迭代

• 100 - 16 = 84次迭代

• 100 - 32 = 68

• - 64 = 36次迭代<

• >F241>

那么我们内部循环的总迭代次数是多少呢？

1. (n-1)
2. (n-1) + (n-2)
3. (n-1) + (n-2) + (n-4)
4. (n-1) + (n-2) + (n-4) + (n-8)
5. etc.

这东西是怎么长出来的？嗯，因为我们知道外部循环将迭代log(n)次，所以我们可以将其表示为求和：

Sum(从对数到i=0 (N)) n-2^i

= i=0 (N)*n-和(从log到log(n)) 2^i

= log(n)*n - (2^0 + 2^1 + 2^2 + ... + 2^log(n))

= log(n)*n -( (1-2^log(n) )/ (1-2) )(实际为2^log(n+1)，但足够接近)

= log(n)*n +1-n

所以现在我们的目标是展示这一点：

对数

(N)*n+1-n= O( log(n)*n )

显然，log(n)*n是O(log(n)*n)，但是1-n呢？

log 1-n =O(

(N)*n)？

1-n log k* <= (N)*n，对于某个k？

设k=1

1-n <= (N)*n？

将n加到两边

1个对数n* <= (N)+ n？是

我们已经证明了f(n)是O(n*log(n))。

证明Big-Omega

既然我们已经使用log( n ) * n得到了f(n)的上界，那么让我们也使用log(n) *n来尝试得到f(n)的下界。

对于下界，我们使用大欧米茄表示法。大欧米茄寻找函数g(n)*k <= f(n)为某个正常数k。

log k(n*

(N)) <= n*log(n) +1- n？

设k= 1/10

N* <= (N)/10 log(N)+1- n？

(n* <= (N)- 10n*log(n)) / 10 log 1- n？

-9n*log(n)/10 <= 1- n？乘以10

-9n*log(n) <= 10 - 10n？乘以-1 (翻转不等式)

9n*log(n) >= 10n - 10？除以9

n*log(n) >= 10n/9 - 10/9？除以n

(N) >= 10/9 - 10/9n ? log(n) log是

显然，当(10/9 - 10/9n)趋于10/9时，数量>= (N)变得更大。实际上，对于n= 1，0 >= 10/9 -10/9.0 log。

证明Big-Theta

现在我们已经展示了f(n) is Big-Omega(n*log(n))。将此与f(n) is O(n*log(n))的证明结合起来，我们已经展示了f(n) is Big-Theta(n*log(n))！(感叹号是为了激动人心，而不是阶乘...)

g(n) =n*(N)，一个有效的常数集合是k1=1/10 (下界)和k2 = 1 (上界)。

Answer 2

为了证明大O:外部循环有floor(log2(n)) + 1 = O(log(n))迭代，内部循环迭代O(n)次per，总共O(n * log(n))次。

为了证明big-Omega:在外部循环中有floor(log2(n/2)) + 1 = Omega(log(n))迭代，在此期间step <= n/2。内部循环迭代n + 1 - step次，对于这些外部迭代，该次数大于n/2 = Omega(n) per，总共为Omega(n * log(n))。

加在一起，big-O和big-Omega证明了big-Theta。

Answer 3

为了简化代码的表示，我们可以将您的代码转换为Sigma表示法

for (step = 1; <= n; step = step * 2) {
    for(i = n; i >= step; step = step - 1) {
    }
}

如下所示：

​

​