最坏情况/最佳情况确认
我想确认我的想法对于以下代码的最坏情况/最佳情况是正确的：
def function2(L, x):
ans = 0
index = len(L)
while (index > 0):
i = 0
while i < 1000000:
i = i + 1
ans = ans + L[index - 1]
index = index // 2
if (x == L[-1]):
return ans
else:
for i in range(len(L)):
ans = ans + 1
return ans
我认为最好的情况是O（sqrt（n）），因为索引// 2是最好的因素。 我认为最糟糕的情况是o（n + sqrt（n）），因为else语句增加了常量运行时间，这是否正确？
我认为最好的情况是O（sqrt（n）），因为索引// 2是最好的因素。
不太清楚你的意思是“索引// 2是最好的因素”。 无论您有什么意见，索引// 2都将成为最佳/最差/平均情况的“因素”。
index将在每次迭代中减半，所以你的循环的复杂度不是sqrt(n)而是log(n) 。 （在这里寻找更详细的解释为什么。）
我认为最坏的情况是o（n + sqrt（n），因为else语句增加了常量运行时。
对使用“O”与“o”非常小心。 Little-o完全是一个完全不同的符号，你不想让他们感到困惑。 （在复杂性中添加n不是添加常量运行时，n是变量而不是常量）
大O是一个包容的上界，因此：
x == L[-1] ，代码运行在O（logn）时间。 x != L[-1] ，第一个循环运行在O（logn）时间，第二个循环运行在O（n）时间。 由于Big-O正在寻找上界，因为我们知道O（n）比O（logn）需要更多的时间，所以我们的复杂度就是O（n）