<分区>
我不明白第二个 for 循环的 T(n) 是 log(n) 的部分。两个回路都由 i 并且令人困惑。代码 O(nlog(n)) 的 T(n) 如何使用基本乘积规则？
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j = j + i)
{
printf("Hi");
}
}
<分区>
我不明白第二个 for 循环的 T(n) 是 log(n) 的部分。两个回路都由 i 并且令人困惑。代码 O(nlog(n)) 的 T(n) 如何使用基本乘积规则？
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j = j + i)
{
printf("Hi");
}
}
最佳答案
对于 i=1，内循环执行 n 次。对于i=2，内部循环执行n/2 次，依此类推。运行时间为 T(n) = n + n/2 + n/3 + ... + n/n。这等于 n(1 + 1/2 + 1/3 + ...+ 1/n) = nH(n) 其中 H(n) 是n次谐波数。 H(n) ~ lg n 因此运行时间为 O(n lg n)。
关于c - 代码O(nlog(n))的T(n)如何？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26202317/