假设我有一些Python列表,my_list其中包含N个元素.可以通过使用索引单个元素my_list[i_1],其中i_1是所需元素的索引.然而,Python列表也可被编入索引my_list[i_1:i_2],其中一个从列表中的"片" i_1,以i_2期望.切割大小为N的列表的Big-O(最坏情况)符号是什么？
就个人而言,如果我被编码"切片"我会从迭代i_1到i_2,产生一个新的列表,并返回它,这意味着O(N),这是Python的是如何做的？
谢谢,
切片Python字符串的时间复杂度是多少？鉴于Python字符串是不可变的,我可以想象将它们切片为O(1)或者O(n)取决于切片的实现方式.
我需要编写一个迭代一个(可能很大)字符串的所有后缀的函数.我可以通过将后缀表示为整个字符串的元组加上一个开始读取字符的索引来避免切片,但这很难看.如果相反,我天真地写这样的函数:
def do_something_on_all_suffixes(big_string):
for i in range(len(big_string)):
suffix = big_string[i:]
some_constant_time_operation(suffix)
... ...将其时间复杂度是O(n)或,其中是？O(n2)nlen(big_string)