分析運行時間，大O

Question

我遇到了算法的時間複雜性問題。

例如下面的Haskell代碼，它將對列表進行排序。

sort xs 
|isSorted xs= xs 
|otherwise= sort (check xs) 
    where 
    isSorted xs=all (==True) (zipWith (<=) xs (drop 1 xs)) 
    check [] =[] 
    check [x]=[x] 
    check (x:y:xs) 
     |x<=y = x:check (y:xs) 
     |otherwise=y:check (x:xs) 

所以對於n是列表和t_isSorted（n）的運行時間函數的長度：有一個恆定T_DROP（N）= c和T_ALL（N）= N，t_zipWith（N）= N ：

t_isSorted(n)= c + n +n 

對於t_check：

t_check(1)=c1 

    t_check(n)=c2 + t_check(n-1), c2= for comparing and changing an element 
      . 
      . 
      . 
    t_check(n)=i*c2 + tcheck_(n-i), with i=n-1 
      =(n-1)*c2 + t_check(1) 
      =n*c2 - c2 + c1 

而且究竟如何我一定要那些拿到t_sort（n）的結合？我想在最壞的情況下，排序xs必須運行n-1次。

Answer 1

isSorted確實是O(n)，因爲它主要是zipWith，而它又是O(n)，因爲它對它的論點進行了線性傳遞。

check本身是O(n)，因爲它只在每次執行時調用一次，並且它總是從列表中刪除恆定數量的元素。最快的排序算法（不知道更多關於列表的內容）在O(n*log(n))（相當於O(log(n!))時間）中運行。這是一個數學證明，而且這個算法更快，所以它不可能將整個列表排序。

check只能動一步;它實際上是一次冒泡排序。

考慮對該列表進行排序：[3,2,1]

check [3,2,1] = 2:(check [3,1]) -- since 3 > 2 
check [3,1] = 1:(check [3]) -- since 3 > 1 
check [3] = [3] 

這將返回 「分類」 列表[2,1,3]。

然後，只要列表沒有排序，我們循環。由於我們可能只會將一個元素放在正確的位置（因爲上述示例中爲3），所以我們可能需要O(n)循環迭代。

這總計爲O(n) * O(n) = O(n^2)

Answer 2

時間複雜度時間複雜度爲O(n^2)。

你是對的，一步需要O(n)時間（對於isSorted和check函數）。它被稱爲不超過n次（甚至可能是n - 1，對於時間複雜度它並不重要）（在第一次調用之後，最大的元素保證是最後一個元素，對於第二次調用後的最大元素我們可以證明最後的k元素是最大的，並且在調用k之後正確排序）。它只交換相鄰的元素，所以每步最多隻消除一個反轉。由於最壞情況下的反演次數爲O(n^2)（即n * (n - 1)/2），因此時間複雜度爲O(n^2)。