Python的sort()/ sorted()函数是否调用其可选的'key'参数O(n)次或O(n log n)次？

Question

假设apples是一个n个苹果的列表,我有一个apple_evaluator(apple)评估苹果'良好'的功能.apples按"善" 排序我用apples.sort(key = apple_evaluator)或sorted(apples, key=apple_evaluator).

将apple_evaluator得到所谓O(n)的时间(如Python的预先计算apple_evaluator(apple) 每个apple在apples随后各种apples使用这些值),或者为O(n log n)的时间(如Python的单位计算重新计算apple_evaluator每个排序使得比较时间值)？

Answer 1

试试看:

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).