最坏情况下的运行时采用Big-Theta表示法

Question

以下代码的最坏情况运行时是什么？该代码从家庭作业分数列表中计算出家庭作业分数的平均值，然后将最低分数降到最低。

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次迭代。

我想知道，对于整个程序的整体运行时，我们是否使用max(Θ(n)，Θ(n)) =Θ(N)，就像使用大O符号，即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仍然具有线性增长。这就是为什么我们忽略了任何大-O/θ的缩放常数。

Answer 2

与大O表示法一样，常数因子也被删除了.所以整个运行时都是Θ(2n) = Θ(n)。

另外，有两个循环并不意味着更长的运行时间，因为循环可以更短，或者每次迭代执行的次数更少。您的第二个程序每次迭代会执行更多的操作，因此总的运行时将大致相同。

Answer 3

您不会在迭代完成之前返回，这意味着您总是要查看完整的列表