algorithm - Big-Theta 表示法中的最坏情况运行时

Question

以下代码在 Big-Theta 表示法中的最坏情况运行时间是多少？代码计算家庭作业分数列表中的最低分数后的平均家庭作业分数。

m := 1
for i := 2 to n
    if h_i < h_m then m := i
total := 0
for j := 1 to n
    if j != m then total := total + h_j
return total/(n − 1)

在最坏的情况下，这意味着最低分位于最后位置。这意味着在第一个循环中，它将运行 n-1 次迭代。第一个循环的上限和下限分别是 O(n) 和 Ω(n)。我相信这意味着它的运行时间为 Θ(n)

第二个循环几乎是一样的，除了它是 n 次迭代。

我想知道整个程序的整体运行时间，我们是否像使用大 O 符号那样使用 max(Θ(n),Θ(n)) = Θ(n)，即 max (O(n), (O(1)) = O(n)？

我问这个问题是因为据说我修改了上面的代码以仅在一个循环上运行:-

m := 1 ; total = h_1
for i := 2 to n
    if h_i < h_m then m := i
    total = total + h_i
total = total - h_m
return total/(n − 1)

此代码还运行 n-1 次迭代 => Θ(n)。现在这对我来说似乎很奇怪，因为显然第一个代码的运行时间比第二个代码更长，因为它有两个循环。这就是为什么我问使用 max (Θ(f(n)) , Θ(g(n)) 是否正确。

Answer 1

您陷入了一个常见的错误，认为大 O/θ 表示法告诉您运行时间。它不会，它会告诉您运行时将如何(渐进地)作为 n 的函数进行扩展。如果算法 1 在 n 中线性增长，而算法 2 的运行时间是算法 1 的两倍，则算法 2 仍然呈线性增长。这就是我们忽略 big-O/θ 的任何缩放常数的原因。