Calculate Big Theta Notation Bubble排序

我正在尝试计算气泡排序的theta表示法，但我陷入困境。鉴于此过程（伪）：Calculate Big Theta Notation Bubble排序

procedure BUBBLE_SORT(A,n) { 
    array A(1 to n) 
    for (int i = 1; i <= n; i++) { 
     for(int j = 1; j <= n-1; j++) { 
      if(A[j] > A[j+1] { 
       //swap(A(j), A(j+1)) 
      } 
     } 
    } 
}

我能得到的运行时间与西格玛符号最坏的情况是：

（N^2 - N）/ 2

为了获得最佳情况下的运行时间，我跟着我的书，这样做：

鉴于p（N）=（N^2 - N）/ 2，我们宣称，p（N）=Θ（N^2）。为了证明这一点，我们表明，对于一些常数C1，C2和N0：

C1N^2 < =（N^2/2）+由（N/2）< = C2N^2

除以两侧N^2，我们得到：

C1 < =（1/2）+（1/2n）后< = C2

这是我迷路。在书中，作者挑选了一些数字，插入并说：“因此，它遵循p（n）=Θ（n^2）”

我怎么知道插入什么数字？我可以插入任何数字吗？如果这些数字符合不等式，这是否意味着我可以立即说算法是Θ（n^2）？

谢谢！

我跟随

来源

2017-08-30 Katrina

你是对的！感谢您指出。现在编辑 – Katrina

的一般做法是，先检查标准的复杂性值。像 2^(2^n) > n! > 4^n > 2^n > n^2 > nlogn > log(n!) > n > sqrt(n) > (logn)^2 > logn > loglogn > 1

这种方式只是插件n^2现在，如果它满足，然后考虑小于那个值。这样你可以获得紧张的限制。如果它不满足去追求更高的价值。这有助于很多情况。

来源

2017-08-30 14:44:52 coderredoc

@卡特里娜：我实际上提到了插件的合理价值......就是这样。 – coderredoc

请记住，这是关于渐近行为。

我们可以考虑一下作为玩游戏：你的目标是要证明某一个绑定的成立。游戏是这样的：首先，你可以选择常量C1和C2。然后我选择了一个任意的n。如果我能以违反不平等的方式做到这一点，那么你就会失去（这个界限并不成立）。如果我无法做到这一点，即使您不再允许您更改您选择的C1和C2，您就会赢（界限是正确的）。

让我们看一下在所讨论的方程现在：

C1 < =（1/2）+（1/2n）后< = C2

由于n是一个整数（在结束时，它代表数组中元素的数量），有一个确定的最小值：n = 1。让我们替代，在：

（1/2）+（1/2）= 1

好了，现在是一个开始。让我们看看会发生什么，因为我会让n变大......请注意，n只出现在分母中。所以我不能因为任意大而弄乱你的界限。最糟糕的情况是你的小的值为n。随着更大的价值n该产品的第二部分变得更小，并最终消失。对于限制n->inf我们得到：

LIM N-> INF（1/2）+（1/2n）后

（1/2）+ LIM N-> INF（1/2N）=（1/2）+ 0 = 1/2

那么，它告诉我们是，无论哪个的n值I进行选择，所得到的值将总是是1/2到1（因为方程是线性的范围内这两个样本足以证明这一点;对于更复杂的方程组，建立边界通常需要多一点工作）。

有了这些知识，你可以选择C1和C2，我永远不会赢得比赛吗？

来源

2017-08-30 15:04:19 ComicSansMS

谢谢你的明确解释:)当计算Θ时，我们总是取n = 1吗？并且表明存在C1和C2的界限足以说明它是Θ（n^2）？如果说我可以找到一个例外，那会不会让Θ（n^2）？ – Katrina

Q1：你需要弄清函数的渐近行为，所以通常你只对大'n'感兴趣。最后，你不必从字面上选择常量，你只需要证明它们存在。 Q2：如果你选择的每个“C1”和“C2”，我总能找到一个违反不等式的n，这个界限是错误的。当然，如果你在选择它们时做了一件糟糕的工作，我总是可以拿出一个n。但是由于我们在这里处理的是一个存在的证明，这足以证明可以以我永远不会赢的方式选择C1和C2，无论我选择哪一个。 – ComicSansMS

谢谢！很好的解释:) – Katrina

我们有兴趣在寻找C1和C2使得下列适用于每一个n >= 1：

C1 <= (1/2) + (1/2n) <= C2

为C1 = 1/2一个很好的选择（但任何严格正值小于也是有效的，例如C1 = 0.1 ）。

C2 = 1的一个不错的选择（但是任何大于该值的值也是有效的）。值C2 = 1是好的，因为表达式1/2 + 1/2n随着n变大而减小，因此其最大值为n = 1。

最后一点：它上面有一些常量C1和C2为其不平等始终保持n >= 1时表示。如果它更方便，我们可以将注意力集中在从另一个常量值（而不是1，例如）开始的n的值。重要的是有一些常数C1和C2，这样当n足够大时，两个不等式都成立。

来源

2017-08-30 15:12:59 qwertyman

Calculate Big Theta Notation Bubble排序

回答

相关问题