添加日志中渐近分析 [英] Adding a log in asymptotic analysis

问题描述

有一个问题，我想工作，通过和将非常AP preciate一些帮助！什么是... ...的时间复杂度

Have a problem I'm trying to work through and would very much appreciate some assistance! What's the time complexity of...

for (int j = 1 to n) {
    k = j;
    while (k < n) {
        sum += a[k] * b[k];
        k += log n;
    }
}

外循环运行n次。我不知道该如何处理 K + =在内部循环日志ñ。我的想法是，这是为O（n ^ 2）。添加的log（n）的k倒不得到一个额外的N循环，但我认为这是不到为O（n * log n）的会。很显然，这只是一个猜测，并找出如何证明数学会大大AP preciated任何帮助！

The outer for loop runs n times. I'm not sure how to deal with k+= log n in the inner loop. My thought is that it's O(n^2). Adding log(n) to k isn't quite getting an additional n loops, but I think it is less than O(n*log n) would be. Obviously, that's just a guess, and any help in figuring out how to show that mathematically would be greatly appreciated!

推荐答案

您可以把的log（n）作为一个恒定在这里，排序。

You can treat log(n) as a constant here, sort of.

在循环的每次迭代将执行工作的一个恒定的量（之和+ = ...; k + = ... ）的次数等于 N / 的log（n）。有循环 N 迭代。因此，总的工作是 N ^ 2 /数（N）。

Each iteration of the loop will perform a constant amount of work (sum+=...; k+=...) a number of times equal to n/log(n). There are n iterations of the loop. The total work is thus n^2 / log(n).

你看到一堆作业，像这样的任何时间：

Any time you see a bunch of operations like so:

 ---------------------b-------------------------
 |O(blah) + O(blah) + O(blah) + O(blah) + O(blah)
 |O(blah) + O(blah) + O(blah) + O(blah)     .
a|O(blah) + O(blah) + O(blah)               .
 |O(blah) + O(blah)                         .
 |O(blah)     .         .         .         .

是 A * B * O（废话） - 试想广场（这里我把 S）。这是一个2D矩形的固定比例（半矩形），因此 0（A * B）。

It is a*b * O(blah) -- just imagine the square (where I put the .s). It is a constant fraction of a 2D rectangle (half of a rectangle), hence the O(a*b).

在上述情况下，B = N ，A = N /日志（N）和O（等等）= O（1）（从内环）

In the above case, b=n, a=n/log(n), and O(blah)=O(1)(from the inner loop)

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