根据 theta 评估以下代码的时间复杂度

Question

我知道时间复杂度是 n*log(n) ，但是我只能用积分来评估它，以便内循环获得上限，我如何获得下限？ 使它成为θ而不是O？

S=0;
for( i=1; i<n; i++)
for( j=0;j<n;j+=i)
S++;

所以第 1 行执行一次，第 2 行执行 n-1 次 + 1 次检查而不输入，这 n-1 次中的每一个第 3 行执行 N/I 次，我们得到： T= 1 + n + (n/1+n/2+...+n/n-1) =<1+n+n (1/x 从 1 到 n 的积分) = 1+n+n log(n)。那是大O，欧米茄呢？

Answer 1

让我们按以下方式分解函数：T(n) = 1 + n + n + n*S(n)，其中S = sum(1/x from x=2 to n-1)。请注意，它与您编写的内容相同。

函数f(x) = 1/x单调递减，因此您可以将S的总和绑定int(1/x from x=1 to n-1)，从下方绑定int(1/x from x=2 to n)。在这两种情况下，您都可以log(n)恒定条款。对于下限log(n-1)-log(1) = log(n-1)和下限log(n)-log(2)。

如果这些边界不明显，则绘制递减函数的积分的左黎曼和和右黎曼和。

顺便说一下，您在问题中确实使用了下限，而不是上限。(因为1/x正在减少，而不是增加。

然后将其添加回表达式中，以便T(n)我们有T(n) >= 1 + 2n + n log(n) - n log(2)和T(n) <= 1 + 2n + n log(n-1)。两者都与n log(n)渐近成正比，给你θ类。