1]的时间和空间复杂性

b1payxdu  于 2021-08-20  发布在  Java
关注(0)|答案(1)|浏览(330)

考虑下面的代码:

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

反转字符串是o(n)。当我们执行x[::-1]时,我假设python只是从最后一个到第一个选择字符串的索引。他做了n次(n=字符串的长度)。因此,说“x=x[::-1]”是正确的吗
时间复杂度的o(n)
o(n)是空间复杂度(必须为新反转的字符串重新分配内存)
如果没有赋值('x[::-1]”),时间复杂度就是o(n),空间复杂度就是o(1)?

3htmauhk

3htmauhk1#

它的时间和空间复杂度都是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_SLICEBINARY_SUBSCR . 唯一的区别是 foo1 然后呢 RETURN_VALUE 虽然 foo2POP_TOP 若要放弃该值,则 LOAD_CONST 装载 None 做之前 RETURN_VALUE .

相关问题