如何计算最佳案例时间复杂度

Question

如何找到 2n²、3⋅log₂(n) 和 2n² + 10n 等公式的最佳用例时间复杂度？具体流程是什么？

Answer 1

对于固定公式，最佳、平均和最差情况是相同的。复杂度为

• 2n² ∈ Θ(n²)
• 3⋅log₂(n) ∈ Θ(log n)
• 2n² + 10n ∈ Θ(n²)

算法可能具有最佳情况复杂度，这取决于输入。 例如。看看冒泡排序。

Input: A[0..n-1] 

switched = false;
for(i = 0; i < n; i++)
{
   switched = false;
   for(j = 0; j < n-i-1; j++)
   {
      if(A[j] > A[j+1])
      {
         switch(A,j,j+1);
         switched = true;
      }
   }

   if(!switched)
      break;
}

最坏的情况是一个从大到小的排序列表，这会导致 O(n²) 的复杂度。但是如果你的输入是一个从小到大的排序列表，算法只执行内部 for 循环一次，因为它不需要切换元素，算法终止。这为您提供了 O(n).

的最佳案例复杂度