当我为不同大小的输入绘制以下算法所需的时间时,时间复杂度似乎是多项式的。我不确定是哪种操作导致了这种情况。
我假设它与list(s)
,del l[i]
和l[::-1]
有关,但我不清楚它们各自的复杂性是什么。有谁能解释一下吗?
另外,有没有一种方法可以在不完全改变方法的情况下优化算法?(我知道有一种方法可以通过使用“双端钳形运动”将其降低到线性时间复杂度。)
def palindrome_index(s):
for i, c in enumerate(s):
l = list(s)
del l[i]
if l[::-1] == l:
return i
return -1
发布于 2020-05-31 17:10:32
你的算法在len(s)
中确实是二次的
在迭代i中,您在长度上执行线性时间操作:创建列表,反转它,以及(平均而言是线性的)擦除元素i。由于您执行此len(s)
时间,因此它在len(s)
中是二次的。
我假设它与
,del li和l::-1有关,但我不清楚它们各自的复杂度是多少。有谁能解释一下吗?
这些操作中的每一个都是线性时间(至少平均而言,这足以分析您的算法)。无论是从可迭代列表还是通过反转现有列表来构造列表,列表的长度都是线性的。删除元素i至少需要n-i+1个元素的移位,因为每个元素都向后移动一次。
发布于 2020-05-31 17:25:46
所有这些都是线性的"O(n)":
list(s)
list(s)
从s
创建一个新列表。为此,它必须遍历s
中的所有元素,因此它的时间与s
的长度成正比。
l[::-1]
就像list(s)
一样,l[::-1]
使用与l
相同的元素创建一个新列表,但顺序不同。它必须接触每个元素一次,所以它的时间与l
的长度成正比。
del l[i]
为了删除位置i
的元素,必须将位置i+1
的元素移动到位置i
,然后将位置i+2
的元素移动到位置i+1
,依此类推。因此,如果您要删除第一个元素(del l[0]
),它必须触摸列表中的移动元素,如果您要删除最后一个(del l[-1]
)元素,它只需删除最后一个。平均而言,它将移动n/2
元素,因此它也是线性的。
https://stackoverflow.com/questions/62113901
复制相似问题