创建列表时检查列表中值的复杂性
Complexity of checking value in a list while creating list
以下代码的最坏情况时间复杂度是多少：
temp_lst = [(1, "one"), (2, "two"), (3, "three")]
if 5 not in [i[0] for i in temp_lst]:
print("5 is not here")
我的理解是 O(n^2) 因为你们在搜索这个列表时都在构建一个列表，所以等效的是在另一个列表中使用某种 for 循环for 循环。
假设n表示temp_lst的长度，那么这段代码的时间复杂度为O(n)。
list comprehension [i[0] for i in temp_list]相当于下面的循环，显然是O(n):
result = []
for i in temp_lst:
result.append(i[0])
结果列表具有相同的长度，n，因此表达式 5 not in ... 实现为 linear search，也采用 O(n)次.
列表理解和线性搜索是一个接一个地进行的，所以我们应该加，而不是乘：O(n) + O(n ) = O(n).
这是线性的--构建一次查找列表并遍历一次。 O(2n) 减少到 O(n)。
话虽如此，这似乎是一个有问题的设计，我认为它是一种反模式，没有任何进一步的信息。如果元组确实按顺序编号且唯一，那么这种结构更有意义
temp_lst = ["one", "two", "three"]
现在，我们可以简单地说 if 5 < len(temp_lst) 并且我们有 O(1) 查找时间。不仅如此，代码更简单，没有冗余信息。如果您需要 1 索引，请在列表的前面添加一个 None 或从所有查找中减去 1。
如果数字不是连续的并且会在列表中留下空洞，那么 dict 可能是合适的结构：
users = {"51232": "bob", "12342": "amy", "17652": "carol"}
同样，按 id 搜索时我们的查找时间为 O(1)，"51232" in users。
以下代码的最坏情况时间复杂度是多少：
temp_lst = [(1, "one"), (2, "two"), (3, "three")]
if 5 not in [i[0] for i in temp_lst]:
print("5 is not here")
我的理解是 O(n^2) 因为你们在搜索这个列表时都在构建一个列表，所以等效的是在另一个列表中使用某种 for 循环for 循环。
假设n表示temp_lst的长度，那么这段代码的时间复杂度为O(n)。
list comprehension [i[0] for i in temp_list]相当于下面的循环，显然是O(n):
result = []
for i in temp_lst:
result.append(i[0])
结果列表具有相同的长度，n，因此表达式 5 not in ... 实现为 linear search，也采用 O(n)次.
列表理解和线性搜索是一个接一个地进行的，所以我们应该加，而不是乘：O(n) + O(n ) = O(n).
这是线性的--构建一次查找列表并遍历一次。 O(2n) 减少到 O(n)。
话虽如此，这似乎是一个有问题的设计，我认为它是一种反模式，没有任何进一步的信息。如果元组确实按顺序编号且唯一，那么这种结构更有意义
temp_lst = ["one", "two", "three"]
现在，我们可以简单地说 if 5 < len(temp_lst) 并且我们有 O(1) 查找时间。不仅如此，代码更简单，没有冗余信息。如果您需要 1 索引，请在列表的前面添加一个 None 或从所有查找中减去 1。
如果数字不是连续的并且会在列表中留下空洞，那么 dict 可能是合适的结构：
users = {"51232": "bob", "12342": "amy", "17652": "carol"}
同样，按 id 搜索时我们的查找时间为 O(1)，"51232" in users。