Space 列表创建的复杂性

Question

谁能解释一下 beyond 程序的 space 复杂性是什么，为什么？

def is_pal_per(str):

s = [i for i in str]
nums = [0] * 129

for i in s:
    nums[ord(i)] += 1

count = 0

for i in nums:
    if i != 0 and i / 2 == 0:
        count += 1

print count

if count > 1:
    return False
else:
    return True

其实我对这行代码很感兴趣。它如何影响上述程序的 space 复杂度？

s = [i for i in str]

nums = [0] * 129

Answer 1

你找到了唯一分配内存的两行：

s = [i for i in str]
nums = [0] * 129

第一个随len(str)线性增长，第二个是常数。因此，你的函数的space复杂度为O(N)，N=str.

的长度

Answer 2

我不清楚你在哪里遇到了问题。 s 只是 str 中单个字符的列表。 space 消耗为 len(s).

nums 是一个常数大小，由 O(N) 项支配。

这段代码是你写的，还是交给你的？编程风格高度不是"Pythonic".

至于你的代码，从这个崩溃开始：

count = 0

for char in str:
    val = ord[char] + 1
    if abs(val) == 1:
        count += 1

print count

return count == 0

首先，我替换了你的单字母变量 (s => char; i => val)。然后我删除了 most 的中间步骤，留下几个帮助您阅读代码。最后，我用了直截了当的布尔值来return，而不是原来的那种绕口令

我没有使用Python的计数方法——那会进一步缩短函数。顺便问一下，你有来打印统一值的计数，还是只需要布尔值 return？如果它只是 return 值，您可以将其缩短。

Space 列表创建的复杂性

Space complexity of list creation

python

algorithm

python-2.7

space-complexity