如何計算最佳案例時間複雜度

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