渐近分析

Question

我无法理解如何将其变成公式.

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j += i) {

我意识到会发生什么,对于每个i ++,你有1级乘法而不是j.

i = 1,你得到j = 1,2,3,...,100

i = 2,你得到j = 1,3,5,......,100

我不确定如何用Big-theta来思考这个问题.

总的j是N,N/2,N/3,N/4 ...,N/N(我的结论)

怎么最好尝试将其视为N的函数？

Answer 1

所以你的问题实际上可以简化为"谐波系列1/1 + 1/2 + 1/3 + ... + 1/N的紧密限制是什么？" 对于这个问题的答案是log N(你可以把它当作连续总和,而不是离散,并注意的积分1/N是log N)

您的谐波系列是整个算法的公式(正如您已正确总结的那样)

所以,你的总和:

N + N/2 + N/3 + ... + N/N = N * (1 + 1/2 + 1/3 + ... + 1/N) = Theta(N * log N)

所以算法的紧密界限是 N*log N

请参阅[严格]数学证明这里(参见"整体测试"和"背离率"部分)