"in"的时间复杂度. (包容运营商) [英] Time Complexity of "in" (containment operator)

问题描述

我只是想知道什么时候理解一种算法的时间复杂度，如下面的算法.

I was just wondering when understanding the time complexity of an algorithm like the one below.

对于python列表，如果我们有一个for循环对其进行迭代，然后进行遏制检查，则其时间复杂度为O(n ^ 2).

For a python list, if we have a for loop iterating over it, and then a containment check, would the time complexity of that be O(n^2).

我知道两者都是O(n)(或者我认为)，所以让它们彼此嵌套会使其变成O(n ^ 2)吗?

I know both are O(n) (or I think) so having them nested in one another would that make it O(n^2)?

我认为，如果此列表"实际上是一个列表，则下面代码的时间复杂度为O(n ^ 2).但是，如果它是字典，它将是O(n)，因为查找是O(1).正确吗?

I think if this "list" is actually a list, then the time complexity of the code below is O(n^2). But if it's a dictionary it would be O(n) because lookup is O(1). Is that correct?

感谢您的任何帮助！

for element in list:
    if x in list:

推荐答案

您的分析是正确的.

• 列表包含为O(n)，执行O(n)次操作O(n)次为O(n ² ).
• 字典查询为O(1)，进行O(1)次操作O(n)次为O(n).

这篇关于"in"的时间复杂度. (包容运营商)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！