当 x 在字符串中时，x[::-1] 的时间和 space 复杂度

Question

考虑以下代码：

x = 'some string'
x = x[::-1]

反转字符串的复杂度为 O(n)。当我们执行 x[::-1] 时，我假设 python 只是从最后到第一选择字符串字符的索引。他这样做了n次。（n = 字符串的长度）。因此说“x = x[::-1]”是正确的：

O(n) 时间复杂度
O(n) 是 space 复杂度（必须为新反转的字符串重新分配内存

如果没有赋值 ('x[::-1]')，时间复杂度仅为 O(n)，space 为 O(1) ?

Answer 1

时间和 space 复杂度均为 O(n)。 Python 优化代码的情况很少见。例如，它将优化 if False: 代码。但是对于这样的事情它不会。

考虑这两个函数：

def foo1(x):
    return x[::-1]

def foo2(x):
    x[::-1]

现在查看这两个函数的“反汇编程序”输出：

>>> dis.dis(foo1)
  2           0 LOAD_FAST                0 (x)
              2 LOAD_CONST               0 (None)
              4 LOAD_CONST               0 (None)
              6 LOAD_CONST               2 (-1)
              8 BUILD_SLICE              3
             10 BINARY_SUBSCR
             12 RETURN_VALUE
>>> 
>>> dis.dis(foo2)
  2           0 LOAD_FAST                0 (x)
              2 LOAD_CONST               0 (None)
              4 LOAD_CONST               0 (None)
              6 LOAD_CONST               2 (-1)
              8 BUILD_SLICE              3
             10 BINARY_SUBSCR
             12 POP_TOP
             14 LOAD_CONST               0 (None)
             16 RETURN_VALUE
>>>

如您所见，它们都包括 BUILD_SLICE 和 BINARY_SUBSCR。唯一的区别是 foo1 然后做 RETURN_VALUE，而 foo2 做 POP_TOP 丢弃值，然后 LOAD_CONST 在做之前加载 None RETURN_VALUE.

当 x 在字符串中时，x[::-1] 的时间和 space 复杂度

Time and space complexity of x[::-1] when x in a string

python

time-complexity

space-complexity