python之Python 的 sort()/sorted() 函数调用其可选的 'key' 参数是 O(n) 次还是 O(n log n) 次

假设 apples 是 n 个苹果的列表，我有一个函数 apple_evaluator(apple) 可以评估苹果的“优劣”。要按“好坏”对 apples 进行排序，我使用 apples.sort(key = apple_evaluator) 或 sorted(apples, key=apple_evaluator)。 p>

apple_evaluator 是否会被调用 O(n) 次(例如，Python 会为 apples< 中的每个 apple 预先计算 apple_evaluator(apple)/code> 然后使用这些值对 apples 进行排序)或 O(n log n) 次(例如，每次排序进行比较时，Python 计算都会重新计算 apple_evaluator 值)？