首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >包含列表操作的Python函数的时间复杂度

包含列表操作的Python函数的时间复杂度
EN

Stack Overflow用户
提问于 2020-05-31 17:05:40
回答 2查看 35关注 0票数 0

当我为不同大小的输入绘制以下算法所需的时间时,时间复杂度似乎是多项式的。我不确定是哪种操作导致了这种情况。

我假设它与list(s)del l[i]l[::-1]有关,但我不清楚它们各自的复杂性是什么。有谁能解释一下吗?

另外,有没有一种方法可以在不完全改变方法的情况下优化算法?(我知道有一种方法可以通过使用“双端钳形运动”将其降低到线性时间复杂度。)

代码语言:javascript
运行
复制
def palindrome_index(s):
    for i, c in enumerate(s):
        l = list(s)
        del l[i]
        if l[::-1] == l:
            return i
    return -1
EN

回答 2

Stack Overflow用户

发布于 2020-05-31 17:10:32

你的算法在len(s)中确实是二次的

在迭代i中,您在长度上执行线性时间操作:创建列表,反转它,以及(平均而言是线性的)擦除元素i。由于您执行此len(s)时间,因此它在len(s)中是二次的。

我假设它与

,del li和l::-1有关,但我不清楚它们各自的复杂度是多少。有谁能解释一下吗?

这些操作中的每一个都是线性时间(至少平均而言,这足以分析您的算法)。无论是从可迭代列表还是通过反转现有列表来构造列表,列表的长度都是线性的。删除元素i至少需要n-i+1个元素的移位,因为每个元素都向后移动一次。

票数 1
EN

Stack Overflow用户

发布于 2020-05-31 17:25:46

所有这些都是线性的"O(n)":

代码语言:javascript
运行
复制
list(s)

list(s)s创建一个新列表。为此,它必须遍历s中的所有元素,因此它的时间与s的长度成正比。

代码语言:javascript
运行
复制
l[::-1]

就像list(s)一样,l[::-1]使用与l相同的元素创建一个新列表,但顺序不同。它必须接触每个元素一次,所以它的时间与l的长度成正比。

代码语言:javascript
运行
复制
del l[i]

为了删除位置i的元素,必须将位置i+1的元素移动到位置i,然后将位置i+2的元素移动到位置i+1,依此类推。因此,如果您要删除第一个元素(del l[0]),它必须触摸列表中的移动元素,如果您要删除最后一个(del l[-1])元素,它只需删除最后一个。平均而言,它将移动n/2元素,因此它也是线性的。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/62113901

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档