找出程序的时间复杂度

Question

我正在尝试计算下面算法的时间复杂度。

def f()
    ans = 0
    for i = 1 to n:
        for j = 1 to log(i):
            ans += 1
    print(ans)

问题的link如下： https://discuss.codechef.com/t/multiple-choice-questions-related-to-testing-knowledge-about-time-and-space-complexity-of-a-program/17976（第 4 题）

Answer 1

答案是O(nlogn)

外循环的复杂度为O(n)，而内循环的复杂度为log(n)

Answer 2

添加到另一个答案中，您可以将算法的总运行时间 T(n) 框定为每个 i 值的内循环运行s 的次数从 1 到 n。当 i = 1 时内循环运行s log(1) 次，当 i = 2 时内循环运行s log(2) 次，依此类推。总运行时间然后由总和表示：

T(n) = log(1) + log(2) + log(3) ... + log(n)

一个日志的总和是一个产品的日志：

T(n) =  log(1*2*3...*n)
     <= log(n^n)         (n! <= n^n)
     =  nlog(n)          (log(a^b) = b*log(a))
T(n) <= nlogn

所以运行-time 并不比 nlog(n) 差：它是 O(nlogn)。

您可以做更多的工作来证明 O(nlogn) 的界限很紧，但这通常是没有必要的。（如果您证明 T(n) 的上界为 nlogn，下界为 nlogn，则您已显示紧界。也就是说，您已显示确切的复杂性class，通常用“Big Theta”= Θ 表示法表示。

T(n) = log(1*2*3...*n)
     >= log(n/2*(n/2 + 1)*(n/2 + 2)...*n)     (throwing away first half of product)
     >= log(n/2^(n/2))                        (reducing all terms to n/2)
     =  n/2(log(n/2))
     =  n/2(logn - 1)                         (assuming base 2)             
T(n) >= n/2(logn - 1) = Θ(nlogn)

因此，由于算法的运行时间受 Θ(nlogn) 函数上下限制，其复杂度 class 恰好为 nlogn。

n/2(logn - 1) <= T(n) <= nlogn implies T(n) = Θ(nlogn)

找出程序的时间复杂度

Finding the time complexity of a program

time-complexity