0

私はマージソートを練習していますが、2番目のバージョンが最初のバージョンよりも優れているかどうか知りたいです-インデックスを移動するだけでなく、リストからポップしているので、メモリ要件の観点からのようです

バージョン1：

def mergesort(L):
    if len(L)<=1: return L
    pivot=len(L)/2
    left=mergesort(L[:pivot])
    right=mergesort(L[pivot:])
    i=j=0
    sortedArr=[]
    while i<len(left) and j<len(right):
        if left[i]<right[j]:
            sortedArr.append(left[i])
            i+=1
        else:
            sortedArr.append(right[j])
            j+=1
    return sortedArr + left[i:] + right[j:]

バージョン2

def mergesort(L):
    if len(L)<=1: return L
    pivot=len(L)/2
    left=mergesort(L[:pivot])
    right=mergesort(L[pivot:])
    sortedArr=[]
    while left!=[] and right!=[]:
        if left[0]<right[0]:
            sortedArr.append(left.pop(0))
        else:
            sortedArr.append(right.pop(0))
    return sortedArr + left + right

並列化を行わずに、バージョン1よりも優れていると仮定してバージョン2をさらに改善する方法はありますか？これまでのところ、これら2つのバージョンのメモリ要件をどのように説明しますか？

4

2 に答える 2

0

listLの場合、L[:n]操作はPython のO(n)時間、スペースです (要素を含む新しいリストを作成します)。O(n)n

a、b、cリストが与えられた場合、a + b + cはO(n)時間と空間であり、場所nは(要素len(a) + len(b) + len(c)を含む新しいリストも作成します)。n

したがって、 への各呼び出しには、時間とスペースmergesort()が必要です。T(n) = 2T(n/2) + O(n)T(n) = O(n*log(n))

2番目のバージョンは、操作が原因で時間の複雑さが悪化しleft.pop(0)ていO(len(left))ます。2 番目のバージョンのメモリ要件は、最初のバージョンと漸近的に同じです。

これは、同じ構造のO(n*log(n))時間O(n)空間ソリューションです (Python 3.3+ 構文を使用):

def mergesort(L):
    return list(merge_sort_gen(L, 0, len(L)))

def merge_sort_gen(L, start, n): # O(n*log(n)) time, O(n) space
    if n == 1:  # a list of one element is always sorted
        yield L[start]
    elif n > 1: # sort halves and merge them
        half = n // 2
        yield from merge(merge_sort_gen(L, start, half),
                         merge_sort_gen(L, start + half, n - half))

Whereは、 merge()2 つのソートされた反復子をマージします。heapq.merge()または次を使用できます。

from functools import partial

def merge(sorted_a, sorted_b, done=object()): # O(n) time, O(1) space
    next_a, next_b = partial(next, sorted_a, done), partial(next, sorted_b, done)

    a, b = next_a(), next_b()
    while a is not done and b is not done:
        if b < a:
            yield b
            b = next_b()
        else:
            yield a
            a = next_a()

    item, rest = (a, sorted_a) if b is done else (b, sorted_b)
    yield item #XXX at least one of sorted_a or sorted_b must be non-empty
    yield from rest

Python Tutor でコードを段階的にたどることができます。

yield from iterable以下と同じアイテムを生成します (ただし、内部の詳細は異なります):

for item in iterable:
    yield item

Pythonyieldキーワードの説明を参照してください。

于 2013-03-23T10:42:08.367 に答える