当我们只存储所有可能的字母表时，为什么答案的最佳 space 复杂度为 O(n)？

Question

我已经写了一个问题的解决方案：“给你一个非空字符串和一个键，k 是一个正整数值。你被要求移动字符串中的每个字符根据字母表的 k 个值。"

例如，如果 k=2 和 string = "abcd" -> "cdef"。对于大于 'z' 的任何顺序，我们需要**环绕字母表**。即如果 string= "zzz" 和 k=2 那么输出应该是 "bbb".

我的解决方案是使用字典来存储字母表中所有字符的ord()，然后对于string中的每个字符只需将k添加到顺序和returns相应的字符来自词典：

def caesarCipherEncryptor(string, key):
    my_dict = dict()
    for i in range(97, 123):
        my_dict[ord(chr(i)) - ord("a")] = chr(i)

    res = ""
    for i in range(len(string)):
        finder = (ord(string[i]) - ord("a")) + key
        while finder > 25:
            finder = finder % 26
        res += my_dict[finder]

    return res

上面的代码通过了所有的测试用例，所以这不是问题。但是，有人告诉我这个问题的最佳 space complexity 是 O(n)，但是顺便说一句，我已经在上面解决了，这不是 O (1)?因为我很简单地将字母表中的所有字符（最多 26 个）存储在我的字典中？

Answer 1

space 的复杂度是 O(n)，因为如果字母表中有更多字母，或者您试图扩展此程序，则您也必须插入所有这些字母。因此，对于 n 个字母的 space 问题，您使用的是 space 的 n 个字节，这意味着 space 复杂度为 O(n)

当我们只存储所有可能的字母表时，为什么答案的最佳 space 复杂度为 O(n)？

Why is the optimum space complexity of the answer O(n), when we are only storing all possible alphabets?

python

string

space-complexity