Big-theta界限,算法分析

Question

我正在努力学习如何找到各种算法的大角度范围,但我很难理解如何做到这一点,即使在阅读了这里的一些问题以及有关该主题的讲座和教科书之后.所以举个例子

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在数组a中的索引数量方面的增加数量上的big-theta界限.我可以看到外部循环本身经历了log(n)次迭代,但我无法弄清楚如何表达内部循环中发生的事情.有没有人有解释或甚至可能尝试咨询的资源？

Answer 1

Big Theta表示法要求我们找到2个常数k1和k2,使得对于足够大的n,我们的函数f(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.

就Big-O表示法而言(其中f(n)<= g(n)*k),你的算法f(n)是O(log(n)*n),在这种情况下g(n)= log(n)*n.

我们来证明这一点:

找到内循环执行

外循环执行多少次？跟踪"步"变量:假设n为100:

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

这是输入100的7次执行.我们可以等效地说它执行(log n)时间(实际上是floor(log n)次,但log(n)就足够了).

现在让我们看一下内循环.跟踪i变量,该变量从每次迭代的开始n和减少开始.因此,对于步骤的每个值,内部while循环将执行n步时间.step

例如,何时 n = 100

• 100 - 1 = 99次迭代
• 100 - 2 = 98次迭代
• 100 - 4 = 96次迭代
• 100 - 8 = 92次迭代
• 100 - 16 = 84次迭代
• 100 - 32 = 68次迭代
• 100 - 64 = 36次迭代

那么内循环的总迭代次数是多少？

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. 等等

这件事怎么会增长？好吧,因为我们知道外循环会迭代log(n)次,所以我们可以将这个东西表示为求和:

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

= log(n)*n - 总和(从i = 0到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

所以现在我们的目标是表明:

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

很明显,log(n)*n是O(log(n)*n),但是1-n呢？

1-n = O(log(n)*n)？

1-n <= k*log(n)*n,对于某些k？

设k = 1

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

向两侧添加n

1 <= n*log(n)+ n？是

所以我们已经证明f(n)是O(n*log(n)).

证明大欧米茄

现在我们使用log(n)*n在f(n)上有一个上界,让我们尝试使用log(n)*n得到f(n)的下界.

对于下限,我们使用Big Omega表示法.对于某些正常数k,Big Omega寻找函数g(n)*k <= f(n).

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

设k = 1/10

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

(n*log(n) - 10n*log(n))/ 10 <= 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

log(n)> = 10/9 - 10/9n？是

显然,数量log(n)随着(10/9-10/9n)倾向于10/9而变大.事实上,对于n = 1,0> = 10/9 -10/9.0> = 0.

证明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*log(n),一组有效常数是k1 = 1/10(下界),k2 = 1(上界).