我只是想知道何时理解像下面这样的算法的时间复杂度。
对于 python 列表,如果我们有一个 for 循环迭代它,然后进行包含检查,那么时间复杂度是否为 O(n^2)。
我知道两者都是 O(n)(或者我认为),所以将它们嵌套在一起会使它变成 O(n^2) 吗?
我想如果这个“列表”真的是一个列表,那么下面这段代码的时间复杂度就是O(n^2)。但如果它是一本字典,它将是 O(n),因为查找是 O(1)。对吗?
提前感谢您的帮助!
for element in list:
if x in list:
最佳答案
你的分析是正确的。
- 列表包含是 O(n),执行 O(n) 次 O(n) 次是 O(n2)。
- 字典查找的复杂度为 O(1),执行 O(1) 次操作 O(n) 次的复杂度为 O(n)。
关于python - "in"的时间复杂度(包含运算符),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56419144/