python - 是否可以将标准输入附加到 Θ(n) Python 中的列表

Question

我遇到了需要将项目添加到列表的问题。它必须使用标准输入，并且在 Θ(n) 中。我似乎只能在 Θ(n^2) 中得到它。这是我的代码：

for i in range(int(r1)): # size of list being made
    for line in sys.stdin.readline().strip().split(" "):
        a.append(line)
Input:  Output: [1, 2, 3]
1
2
3

据我所知，这在 Θ(n^2) 中。我试过这样做：

for i in range(int(r1)): # size of list being made
    a.append(sys.stdin.readline().strip().split(" "))
Input:  Output: [[1], [2], [3]]
1
2
3

因为第二次尝试的元素在他们自己的子列表中，所以它们不适用于我的程序的其余部分。有什么建议吗？

标签： pythonpython-3.xstdin

Answer 1

这不在 Θ(n) 中，也不在 Θ(n^2) 中。复杂性取决于许多不同的变量：正在制作的列表的大小以及标准输入每行上的空格数。外层 for 循环执行 list-size 次数；该循环的主体在每行执行 number-of-spaces-on-line 次数。因此，对于 [0, r] 中的所有 i，您的复杂性更像是 Θ(r * k_i)，其中 k_i 是第 i 个标准输入的空格数。