algorithm - 上述算法的平均案例复杂度

Question

寻找最大最小算法的简单线性搜索

maxmin(a,n,max,min)
{
   max=min=a[1];
   for i=2 to n do
   {
     if a[i]>max then
         max:=a[i]; 
     else if a[i]<min then 
         min:=a[i];
    }
}

1.假设第一个 if 条件对 n/2 个元素失败，上述算法的平均情况复杂度

---

给出的答案

n-(n/2)-1(first if 成功的元素数)+ 2 * (n/2)(first if 失败的元素数)= 3n/2 -1

对吗？？但是失败了，为什么要乘以2？？

Answer 1

这是 O(n)。 if 语句和可能的赋值是 O(1)，因此它们不会影响 big-O 分类(尽管它们确实会在某种程度上影响运行时)。

考虑该问题的另一种方法是意识到如果将 N 加倍，则运行时间几乎会加倍。