使用多个函数的时间复杂度？

Question

假设我们一次性使用 2 个函数：

sorted(list(str_variable)) - Python 使用复杂度为 NlogN 的 Timsort - 因此整体复杂度变为：N^2*logN

它会被视为函数内部的函数，因此复杂性将成倍增加（O(N) 代表 list()，O(NlogN) 代表 sort()。

但我也可以这样写：

s = list(str_variable)
res = sorted(s)

在这种情况下它只是 O(N) 使用 O(N + NlogN)?

在这两种情况下，字符串变量都被拆分成单独的字符，然后进行排序 - 因此所用时间应该相同。

Answer 1

不是这样的，首先，list(str_variable)被执行，然后sorted(answer)被执行，本质上，上面的两个函数应该花费相同的时间。

在内部，它正在按照您在第二个代码片段中显示的那样执行，因此您可以使用相同的符号。

你也可以试试这样检查：

import time
now = time.time()
sorted(list(str_variable))
print(time.time() - now )


now = time.time()
s = list(str_variable)
res = sorted(s)
print(time.time() -now)

我敢打赌第一个跑得更快

Answer 2

如果您有嵌套函数调用，它们的复杂性不会成倍增加。

假设您的电话是

f(g(N))

并且 f 和 g 在大小 N 的输入上的时间复杂度分别为 F(N) 和 G(N)。那么总的时间复杂度是

G(N) + F(size(g(N))

在您的示例中，f 是 sorted，g 是 list，因此我们有以下内容：

F(N) ∈ O(N log N)
G(N) ∈ O(N)
size(g(str_variable)) = N

所以总的复杂度是

  G(N) + F(size(g(N))
∈ O(N) + O(N log N)
= O(N log N)    since O(N) ⊂ O(N log N)

使用多个函数的时间复杂度？

Time complexity of using multiple functions?

python

function

time-complexity