1

applesが n 個のリンゴのリストで、リンゴの「良さ」を評価する関数がapple_evaluator(apple)あるとします。apples「良さ」で並べ替えるにはapples.sort(key = apple_evaluator)、 orを使用しますsorted(apples, key=apple_evaluator)。

apple_evaluatorO(n) 回呼び出されるか (たとえば、Pythonapple_evaluator(apple) はそれぞれの値を事前計算してから、これらの値を使用appleしてapples並べ替えます)、または O(n log n) 回呼び出されますか (たとえば、Pythonは、並べ替えが比較を行うたびに値をapples再計算します)?apple_evaluator

4

2 に答える 2

5

テストするだけです：

count = [0]

def _sort_key(x):
    count[0] += 1
    return x


a = list(np.random.rand(12))

print count
a.sort(key=_sort_key)
print count, len(a)

答えは O(n) です。

于 2013-10-14T02:08:31.997 に答える
4

に置き換えることの全体的なポイントは、キー関数への O(n) 呼び出しを持つことでしたcmp。keyこれは、シュワルツ変換または装飾-並べ替え-非装飾として知られています。

パラメータが登場する前は、この手順を実行する方が効率的だったため、ほとんど役に立たないことkeyがわかりました。キー機能はcmpどこですかf

L = [(f(i), i) for i in L]                           ## decorate
L.sort()    # there was no "sorted()" at the time    ## sort
L = [i[1] for in L]                                  ## undecorate
于 2013-10-14T02:49:06.397 に答える