计算大 Theta 符号冒泡排序

Question

我正在尝试计算冒泡排序的 theta 表示法，但我卡住了。给出这个过程（伪代码）：

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))
            }
        }
    }
}

我能够得到最坏情况下的运行时间，使用 sigma 表示法是：

(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

这是我迷路的地方。书中作者挑出一些数字，插上说"Therefore it follows that p(n) = Θ(n^2)"

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

谢谢！

Answer 1

我遵循的一般方法是首先检查标准复杂度值。像 2^(2^n) > n! > 4^n > 2^n > n^2 > nlogn > log(n!) > n > sqrt(n) > (logn)^2 > logn > loglogn > 1

这种方式只是插件 n^2 现在，如果满足则考虑小于该值的值。这样你就可以得到紧束缚。如果它不满足，则寻求更高的价值。这在很多情况下都有帮助。

Answer 2

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

我们可以把它想象成玩游戏：你的目标是证明某个界限成立。游戏是这样的：首先，您可以选择常量 C1 和 C2。然后我可以选择一个任意的 n。如果我能以违反不平等的方式做到这一点，你就输了（界限不成立）。如果我无法做到这一点，即使您不再被允许更改您选择的 C1 和 C2，您也赢了（绑定是正确的）。

现在让我们看看有问题的方程式：

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

由于n是一个整数（归根结底，它代表了你数组中元素的个数），所以有一个确定的最小值：n = 1。让我们将其替换为：

(1 / 2) + (1 / 2) = 1

好的，现在开始了。让我们看看当我把 n 变大时会发生什么......请注意 n 只出现在分母中。所以我不能通过任意大来搞乱你的界限。对您来说最糟糕的情况实际上是 small 值 n。 n 的值越大，乘积的第二部分越小，最终消失。对于极限 n->inf，我们得到：

lim n->inf (1 / 2) + (1 / 2n)

(1 / 2) + lim n->inf (1 / 2n) = (1 / 2) + 0 = 1 / 2

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

有了这些知识，你能不能用我永远赢不了的方式来选择C1和C2？

Answer 3

我们有兴趣找到 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 时不等式总是成立。如果更方便的话，我们可以从另一个常数值开始关注 n 的值（而不是 1，例如 n >= 10000）。重要的是有一些常量 C1 和 C2 因此当 n 足够大时这两个不等式都成立。

计算大 Theta 符号冒泡排序

Calculate Big Theta Notation Bubble Sort

sorting

algorithm

bubble-sort

time-complexity