时间戳

首页 > 解决方案 > 当 x 在字符串中时 x[::-1] 的时间和空间复杂度

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

问题描述

考虑以下代码：

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

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

如果没有赋值 ('x[::-1]')，它的时间复杂度是 O(n)，空间复杂度是 O(1)？

标签： pythontime-complexityspace-complexity

解决方案

它的时间和空间复杂度都为 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。唯一的区别是foo1then does RETURN_VALUE， while foo2doesPOP_TOP丢弃值，然后在 do之前LOAD_CONST加载。NoneRETURN_VALUE

推荐阅读