根据大小为n的输入所需的基元操作，最合适的运行时公式

Question

当从里到外解析时，我得到：

内部循环= 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)

Answer 1

实际上，我在这里提出了O(NlgN)来表示总体运行时间。可以理解，j中的内部循环不依赖于i中的外部循环。以下情况应为真：

• i中的外部循环是O(lgN)，因为i在每次迭代中都是双倍的，这是指数行为。
• j中的内部循环是O(N)，因为无论i.

的值如何，<代码>d12在每次迭代中从0循环到<代码>d13

因此，我们可以将这些复杂性相乘，得到总体复杂性。

请注意，对于任意大小的N，您的表达式：

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

缩减为NlgN。

Answer 2

def rate(n):
    total= 0     
    i = 1        

while i < n: //This outer loop runs O(log(n)) times

        j = 0    

while j < n: //This inner loop runs O(n) times for each iteration of outer loop

            total= i * j + total
            j = j + 1
        i = i * 2
    return total

因此，在big-O中实现的总运行时复杂度是=O((N))* O(n) = O(nlog(n))。