大 O 复杂性 Python，找出运行大小的输入时间 'n'

Question

对于这个函数，我要select最合适的Big-O运行输入大小n的时间：

def 2d_list(n):
    i = 0
    data = []
    while i < n:            
        data.append([i] * n)
        i += 1
    return data

上述函数将一个整数作为参数并创建一个二维整数列表。例如下面的代码片段：

print(2d_list(3))
produces

[[0, 0, 0], [1, 1, 1], [2, 2, 2]]
Select one:

一个。 O(n^3)

b。 O(n)

c。 O(n log n)

d。 O(n^2)

e。 O(log n)

我觉得答案应该是d. 0(n^2)。这样对吗？

Answer 1

while 循环运行的次数与 n 的大小线性相关，并且在每次迭代中，[i]*n 创建一个列表并向其中添加 i n次，又是一次迭代。一个迭代嵌套在另一个迭代中是 O(n^2) 时间复杂度。

Answer 2

None 的给定选项是正确的。让我们稍微重写一下函数：我们只是将参数从 n 重命名为 x:

def 2d_list(x):
    i = 0
    data = []
    while i < x:            
        data.append([i] * x)
        i += 1
    return data

现在我们有多少操作？还有 O(x^2) 操作：对于 i 的每个 x 值，我们必须创建一个包含 x 个元素的列表。

但是输入大小是多少 n？这就是您需要表示数字 x 的位数。数字 x 的增长速度比 n 快得多：您基本上可以将 x 的大小加倍，而无需向输入添加超过 1 位。

因此，您有 n = log x，或 x = 2**n。这意味着你的函数的时间复杂度实际上是 O(4**n).

Answer 3

这个问题具有误导性。输入大小为 log n 即表示 n.

所需的位数

如果我们想根据 n 而不是输入大小来计算复杂度，那么答案是 O(n^2)

如果我们想根据输入大小 s 进行计算，那么答案是 O((2^s)^2) = O(2^(2*s)) = O((2^2)^s)，正如 chepner 所写。

Big O Complexity Python, find out running time for input of size 'n'