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

Question

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

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

维基百科中的更多内容here

Answer 2

排序算法通常在 O(n log(n)) 到 O(n²) 之间。内置排序函数通常是O(n log(n))。您的 for 循环也是 O(n)，因此您算法的时间复杂度为 O(n log(n)) + n)，即 O(n log(n))。

并且因为您在第一行创建了一个新数组，所以内存复杂度为 O(n)

此外，您可以使用散列 table 来改善时间和内存复杂度。

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

What is the time complexity of the following function, that uses buit-in sorted function?

python

time-complexity