渐近分析 [英] Asymptotic analysis

问题描述

我无法理解如何使它成为一个公式。

I'm having trouble understanding how to make this into a formula.

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

我知道会发生什么，因为每个i ++你有乘法少的J为1级。

I realize what happens, for every i++ you have 1 level of multiplication less of j.

I = 1，则得到J = 1，2，3，...，100

i = 1, you get j = 1, 2, 3, ..., 100

设为i = 2，则得到J = 1，3，5，......，100

i = 2, you get j = 1, 3, 5, ..., 100

我不知道怎么想这大-θ的条款。

I'm not sure how to think this in terms of Big-theta.

的总的J是N，N / 2，N / 3，N / 4，...，N / N（我的结论）

The total of j is N, N/2, N/3, N/4..., N/N (My conclusion)

怎么会是最好的尝试，并认为这是N的函数？

How would be best to try and think this as a function of N?

推荐答案

所以，你的问题可以实际降低到什么是紧张开往调和级数1/1 + 1/2 + 1/3 + ... + 1 / N？对于这个问题的答案是日志N （你可以把它当作连续总和，而不是离散，并注意到了 1 / N的积分是日志N ）

So your question can be actually reduced to "What is the tight bound for the harmonic series 1/1 + 1/2 + 1/3 + ... + 1/N?" For which the answer is log N (you can consider it as continuous sum instead of discrete, and notice that the integral of 1/N is log N)

您调和级数的是的整个算法的计算公式（如你正确的结论）

Your harmonic series is the formula of the whole algorithm (as you have correctly concluded)

那么，你的总和：

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

那么紧开往算法 N *日志N

参见[严格]数学证明 href="http://en.wikipedia.org/wiki/Harmonic_series_%28mathematics%29">（见整体测试和率三岔口部分）

See the [rigorous] mathematical proof here (see the "Integral Test" and "Rate of Divergence" part)

这篇关于渐近分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！