1]的时间和空间复杂性

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

考虑下面的代码:

  1. x = 'some string'
  2. 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: 例如,编码。但是像这样的事情就不会了。
考虑这两个功能:

  1. def foo1(x):
  2. return x[::-1]
  3. def foo2(x):
  4. x[::-1]

现在查看这两个功能的“反汇编程序”输出:

  1. >>> dis.dis(foo1)
  2. 2 0 LOAD_FAST 0 (x)
  3. 2 LOAD_CONST 0 (None)
  4. 4 LOAD_CONST 0 (None)
  5. 6 LOAD_CONST 2 (-1)
  6. 8 BUILD_SLICE 3
  7. 10 BINARY_SUBSCR
  8. 12 RETURN_VALUE
  9. >>>
  10. >>> dis.dis(foo2)
  11. 2 0 LOAD_FAST 0 (x)
  12. 2 LOAD_CONST 0 (None)
  13. 4 LOAD_CONST 0 (None)
  14. 6 LOAD_CONST 2 (-1)
  15. 8 BUILD_SLICE 3
  16. 10 BINARY_SUBSCR
  17. 12 POP_TOP
  18. 14 LOAD_CONST 0 (None)
  19. 16 RETURN_VALUE
  20. >>>

如你所见,它们都包括 BUILD_SLICEBINARY_SUBSCR . 唯一的区别是 foo1 然后呢 RETURN_VALUE 虽然 foo2POP_TOP 若要放弃该值,则 LOAD_CONST 装载 None 做之前 RETURN_VALUE .

展开查看全部

相关问题