algorithm - 这段代码的最坏情况时间复杂度是多少？

Question

我在课堂上有一个小测验，但做得不太好。我正在寻找是否有人可以向我解释我在这里做错了什么——当我们搬到网上时，我们的教授忙于办公时间，所以我想我会在这里发帖。

def functionA(n):
    level = n 
    total = 0
    while level > 1:
        for i in range(0,n):
            level = level // 2
            total = total + i
    return total

我的回答：上面的函数是 O(log n) 因为for循环在每次迭代中将 level 变量分成两半。

我得到了 5/10 分，但它并没有真正解释它的错误或正确之处。我做错了什么，为什么？

用于证明测验已评分并返回的图片。只是想弄清楚。

标签： algorithmbig-o

Answer 1

问题是这一行：

for i in range(0,n):

因为n和level是两个完全独立的变量，它们是副本n并且n永远不会改变，所以这个循环总是 O(n)。

一旦我们确定内循环是 O(n)，我们需要弄清楚外循环的复杂性。

在外循环的第一次迭代中，内循环重复设置level = level // 2. 由于这个赋值会很快减少level到 1，所以外循环保证在第一次迭代后终止，使其成为常数时间。

for对于内部循环的单次迭代，我们的整体复杂度为 O(n) 。