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

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