algorithm - 输入n所需的基本操作方面最合适的运行时公式

对于以下代码块，根据输入大小n所需的基本操作选择最合适的运行时公式：
从内到外解决时，我得到：
内环=3N+1
主回路+内环=3+（3n+1）+logn=4+3n+logn
额外步骤+所有循环=4+n（4+3n+logn）=4+4n+3n2+logn
这是要分析的代码：

def rate(n):
    total= 0
    i = 1
    while i < n:
        j = 0
        while j < n:
            total= i * j + total
            j = j + 1
        i = i * 2
    return total

答案应该是-->f（n）=4+4log（n）+log（n）*（3n）

最佳答案

实际上，我在这里给出了整个运行时间的O(NlgN)请注意，j中的内环不依赖于i中的外环。以下应该是正确的：
i中的外环是O(lgN)，因为i在每次迭代时都是加倍的，这是指数行为。
j中的内环是O(N)，因为j在每次迭代时都从0循环到N，而不考虑i的值。
因此，我们可以将这些复杂性相乘以获得整体复杂性。
注意，对于任意大的N，表达式：

4 + 4log(n) + log(n)*(3n)

减少到NlgN。

关于algorithm - 输入n所需的基本操作方面最合适的运行时公式，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57654050/