渐近复杂度 python

Question

我的任务是找出这段 python 代码的渐近复杂度。

for i in range(x):
    if i == 0:
        for j in range(x):
            for k in range(500):
                print("A ")

据我所知应该是 500*x。因为第一个循环只进行一次 (i==0)，第二个循环进行 x 次，第三个循环进行 500 次，所以它应该是 500*x，不是吗？然而，这不是正确的答案。你能帮帮我吗？

Answer 1

渐近复杂度描述了执行时间随着可变因素增长到任意大而增长。简而言之，常数相加或相乘在 all 中不算数，因为它们不随变量改变。

是的，打印了 500*x 行。您还有 x-1 次非功能性循环迭代。您的总时间将计算为

(x-1)[loop overhead] + x[loop overhead] + 500*x[loop overhead + print time]

然而，作为常量的循环开销是微不足道的，并且从复杂性表达式中删除。同样，500 只是一个比例因子，也从表达式中删除。

复杂度为O(x)。

Answer 2

它是 501*x，因为您还必须检查 x 行 if i == 0.

正如其他答案所说，通常我们不包括该因素。但有时我们会这样做。