python - 这个 Big-O 表示法对于这个简单排序函数 (Python) 是否正确？

Question

假设我们有以下函数：

def sort_list(list_of_strings):
    """Take a list of strings, sort the letters in each string,
    and then sort the full list. The list is modified in place."""
    for i in range(len(list_of_strings)):
        list_of_strings[i] = ''.join(sorted(list_of_strings[i]))
    list_of_strings.sort()

O(n)因为函数运行所需的时间长度取决于 的长度，所以说它具有大 O 表示法是否正确list_of_strings？

标签： pythonfunctionbig-o

Answer 1

对大小为 N 的列表进行排序需要 O(N * log(N)) 时间（通常，这取决于确切的输入和使用的算法，但 Python 的内置排序函数不会比这更糟）。

在循环中做某事会使运行时间成倍增加，而按顺序做事意味着将运行时间加在一起。

这意味着，给定N = len(list_of_strings)和M = max(len(string) for string in list_of_strings)，循环的运行时间是 ，后面N * O(M * log(M)) = O(N * M * log(M))的位是O(N * log(N))，这意味着运行时间sort_list是O(N * M * log(M) + N * log(N))。