0

リストを昇順でソートするための私のコードは次のとおりです。関数内で関数を使用しました。ここで、この関数の時間複雑度を計算したいと思います。私の側からは、関数「sort」がループを完了するたびに関数「unite」が呼び出されると計算しました。したがって、この関数では毎回 2 つの関数が使用されます。したがって、この関数の複雑さは O(nlog(n)) であると結論付けました。私はこの章が初めてです。したがって、このタイプの複雑さを計算する方法を知りたいです。上記の答えは私の概算です。そして、私は本当の答えを知りませんし、解決策やヒントもありません。ですから、あなたが与えるときはいつでもあなたの答えを説明してください. ありがとう。これが私のコードです。

def sort(lst):
    def unite(l1, l2):
        if len(l1) == 0:
            return l2
        elif len(l2) == 0:
            return l1
        elif l1[0] < l2[0]:
            return [l1[0]] + unite(l1[1:], l2)
        else:
            return [l2[0]] + unite(l1, l2[1:])

    if len(lst) == 0 or len(lst) == 1:
        return lst
    else:
        front = sort(lst[:len(lst)/2])
        back = sort(lst[len(lst)/2:])

        L = lst[:]  # the next 3 questions below refer to this line
        return unite(front, back)
4

3 に答える 3

0

n 要素ベクトルでソートを実行する時間は T(n) です。

T(n) =  2 T(n/2) + n

     =  2 [2 T(n/4) + n/2] + n

     =  4 T(n/4) + 2n

     = 4 [2 T(n/8) + n/4] + 2n

     = 8 T(n/8) + 3n
     ........

     = 2k T(n/2k) + k n

     = 2log2 n T(1) + (log2n) n   because T(1)=O(1) 

     = n + n log2 n    

     = O(n log n) 

ソート ソリューションの再帰関数の複雑さを覚える簡単な方法があります。T(選択ソート) = O(n^2)、T(マージソート) = O(nlogn)。明らかに、コードはマージソートタイプです。

于 2015-03-09T03:51:27.747 に答える