実行時間の分析、Big 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_checkについては

t_isSorted(n)= c + n +n 

：

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 

そして、どのように正確I（n）はt_sortを取得するために、これらを組み合わせなければならないのですか？私は最悪の場合、ソートxsはn-1回実行しなければならないと思います。

Answer 1

isSortedは実際にはzipWithによって支配されているので、O(n)であり、それはその引数を線形に渡すので、O(n)です。

checkは、実行ごとに1回だけ呼び出すため、O(n)であり、常にリストから一定数の要素を削除します。最速のソートアルゴリズム（リストについて何も知らない）は、O(n*log(n))（O(log(n!))時間に相当）で実行されます。これは数学的に証明されており、このアルゴリズムは高速であるため、リスト全体をソートすることはできません。

checkは1つのステップだけを移動します。効果的にバブルソートの単一パスです。

は、このリストをソート考えてみましょう： "ソート" リスト[2,1,3]を返します[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] 

。

リストがソートされていない限り、ループします。上記の例では3のように1つの要素を正しい位置に配置するだけなので、ループの繰り返しはO(n)必要になることがあります。

これはO(n) * O(n) = O(n^2)

Answer 2

の時間複雑で複雑さがO(n^2)ある時間を合計します。

あなたは正しく、1ステップにO(n)時間（isSortedとcheckの両方の機能）がかかります。 n回（おそらくn - 1でも、時間の複雑さは本当に重要ではありません）（最初の呼び出しの後で最大の要素が最後の要素であることが保証されています。最後にk要素が最大であり、k呼び出し後に適切にソートされていることが証明できます）。それは隣接する要素だけを交換するので、ステップごとに最大で1回の反転を取り除きます。最悪の場合、逆転回数がO(n^2)（すなわち、n * (n - 1)/2）であるので、時間複雑度はO(n^2)である。