凯撒密码加密器最优空间复杂度为何为O(n)？我的实现空间复杂度是否为O(1)？

Great question—let's unpack the space complexity details here, along with why the problem's optimal space complexity is noted as O(n).

1. Your Implementation's Space Complexity #

First, you're absolutely right about your dictionary: since it only stores 26 key-value pairs (one for each lowercase letter), its size is constant—no matter how long the input string is, this dictionary doesn't grow. That means the extra space used by the dictionary is O(1).

The only variable-sized space in your code is the res string, which stores the encrypted result. Since this string has exactly the same length as the input string (n characters), this contributes O(n) space.

Putting it all together:

• Total space complexity: O(n) (dominated by the result string)
• Extra space complexity (space beyond the input and output): O(1) (just the fixed-size dictionary and a few variables)

Your implementation is already efficient in terms of extra space!

2. Why the Problem's Optimal Space Complexity is O(n) #

The key here is distinguishing between total space and extra space.

To solve this problem, you must produce an output string of length n (same as the input). No matter what approach you take, you can't get around storing this result—even if you tried to modify the input string in place (which isn't feasible in Python since strings are immutable), you'd still need to create a new string for the output.

This means the minimal total space complexity for any correct solution is O(n), because you have to account for the output storage. The "optimal" label here refers to total space, since you can't do better than storing the n-length result.

A Minor Optimization for Your Code #

Your code works perfectly, but we can simplify it to avoid the dictionary entirely (since we don't need a lookup table—we can compute the new character directly with arithmetic):

def caesarCipherEncryptor(string, key):
    encrypted_chars = []
    # Reduce key to a value between 0-25 to avoid unnecessary calculations
    key = key % 26
    for char in string:
        original_position = ord(char) - ord('a')
        new_position = (original_position + key) % 26
        encrypted_chars.append(chr(new_position + ord('a')))
    return ''.join(encrypted_chars)

This version still has the same space complexity (O(n) total, O(1) extra), but it eliminates the dictionary and the while loop for modulo operations, making it a bit more efficient and readable.

内容的提问来源于stack exchange，提问作者Patrick_Chong