分析运行时间，大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) 运行ning 时间函数：有一个常数 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 支配，而 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]

return "sorted" 列表 [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)。

分析运行时间，大O

Analysing running time, Big O

algorithm

big-o

haskell

time-complexity