以下使用内置排序函数的函数的时间复杂度是多少？

Question

我正在准备面试，想知道我编写的以下代码中find_missing函数的时间复杂度是多少，它在 1 到 99 之间的未排序值列表中找到缺失值。我对复杂性理论很陌生，而不是确定在使用内置排序函数时如何正确计算它。

def find_missing(num_array):
    num_array = sorted(num_array)
    print(num_array)
    for k in range(len(num_array)-1):
        if num_array[k] == num_array[k+1] - 1:
            continue
        else:
            return num_array[k] + 1

Answer 1

Python 内置排序函数是自定义排序函数调用Timsort，时间复杂度为O(n log n).

更多关于维基百科的内容在这里