時間の複雑さは、Python

Question

に私はPythonで

import sys 

def mergeSort(array): 
    if len(array) < 2: 
     return array 

    middle = len(array)/2 
    left = mergeSort(array[:middle]) 
    right = mergeSort(array[middle:]) 
    return merge(left, right) 

def merge(left, right): 
    result = [] 
    while left and right: 
     if left[0] < right[0]: result.append(left.pop(0)) 
     else: result.append(right.pop(0)) 

    while left: result.append(left.pop(0)) 
    while right: result.append(right.pop(0)) 

    return result 

array = map(int, sys.stdin) 
print mergeSort(array) 

をマージソートを実装しかし、誰かがlist.popの時間計算量は（0）Pythonでの直鎖またはO（n）があることを教えてくれました。その場合、上記のコードはO（n log n）でソートされません。私はそれにどのような変更を加える必要がありますか？

Answer 1

あなたはcollections.dequeを使うことができますが、Timsortを倒すことはありません。

Answer 2

あなたに正しいと言った人。 list.pop()はO（1）ですが、list.pop(0)は線形です。なぜなら、リスト全体をスペースを埋めるためにシフトする必要があるからです。従って、一般に、list.pop(x)はO（n-x）である。 Ignacioが示唆しているように、dequeを使用できます。両端キューからのポッピングは、いずれの側でもO（1）です。 （しかし、中央のO（n）に遅くなります）