如何解决大O符号为素数函数吗？ [英] How to solve Big-O Notation for prime number function?

问题描述

我想了解大O符号。很抱歉，如果我要求的东西是太明显了，但我似乎无法环绕此我的头。

I am trying to understand Big-O Notation. So sorry if I am asking something that is too obvious but I can't seem to wrap my head around this.

我有以下的C＃code，我试图计算大O符号的功能。

I have the following C# code function that I am trying to calculate Big-O Notation for.

for (i = 2; i < 100; i++)
     {
        for (j = 2; j <= (i / j); j++)
           if ((i % j) == 0) break; // if factor found, not prime
        if (j > (i / j)) 
           Console.WriteLine("{0} is prime", i);
     }

现在我走到这一步，是，我认为，无论是如果条款被认为是恒定的O（1），并没有考虑到这个算法的计算？并且，如果我也理解正确的一个for循环

Now what I got so far is that I think that both the if clauses are considered constant O(1) and not taken into account for the calculation of this algorithm? And also if I have understood correctly a single for loop

for(i = 0; i < 100; i++)

，因为它是一个线性函数将是O（n）和一个嵌套循环，不依赖于一个变量从周围环

since it is a linear function would be O(n) and a nested loop that does not depend on a variable from the surrounding loop

for(i = 0; i < 100; i++)
    for(j = 0; j < 100; j++)

是O（n ^ 2）？但如何计算的函数，例如最上面的一个，其中所述第二回路是依赖于第一环路，并创建一个非线性函数？

Is O(n^2)? But how do I calculate a function such as the top one where the second loop is dependent on the first loop and creates a non-linear function?

我发现linearithmic一个定义，说

I found a definition for linearithmic that says

Linearithmic算法可以扩展到巨大的问题。每当ñ双打，   运行时间多（但没有更多）一倍以上。

Linearithmic algorithm scales to huge problems. Whenever N doubles, the running time more (but not much more) than doubles.

虽然这似乎是如何code段运行的一个很好的说明就意味着它是O（N日志[n]）的，如果是这样我怎么能算呢？

While this seems to be a good description of how this code snippet runs would that mean that it is O(N Log[n]) and if so how could I calculate this?

推荐答案

@乔恩是接近，但他的分析是有点错了，你的算法真正的复杂 O（N *开方（N））

@Jon is close but his analysis is a bit wrong, and the real complexity of your algorithm is O(n*sqrt(n)).

这是基于这样的事实，对于每个号码我的'工作'，你应该做的内循环的预期数量为：

This is based on the fact that for each number i, the expected number of 'work' you should do in the inner loop is:

1/2 + 2/3 + 3/4 + ... + (sqrt(i)-1)/sqrt(i) = 
 = 1-1/2 + 1-1/3 + ... + 1-1/sqrt(i)
 = sqrt(i) - (1/2 + 1/3 + ... + 1/sqrt(i)
 = sqrt(i) - H_sqrt(i)

因为 H_sqrt（我）（谐波数）在 O（日志（开方（I））= 0（1/2 *日志（一），我们可以得出结论，复杂性是 0 （开方（我）-log（I））= O（开方（I）），每个素数计算。

since H_sqrt(i) (The harmonic number) is in O(log(sqrt(i)) = O(1/2*log(i), we can conclude that the complexity is O(sqrt(i)-log(i)) = O(sqrt(i)), per prime number calculation.

由于此反复按每个做我，这个问题的总的复杂性是 O（开方（2）+的sqrt（3）+ ... + SQRT（N））。根据这个论坛主题，平方根之和在为O（n * SQRT（N）），这比雪上加霜O（nlogn）。

Since this is done repeatedly per each i, the total complexity of the problem is O(sqrt(2) + sqrt(3) + ... + sqrt(n)). According to this forum thread, the sum of squared roots is in O(n*sqrt(n)), which is "worse" than O(nlogn).

旅游注意：

1. 第一总和高达开方（我），因为这是点 J＆GT; （I / J）。
2. 第一总和（J-1）/ J 每个Ĵ，因为平均一个出来的Ĵ元素正在进入休息（元素的1/3是可分3 1/4 4，...），这给我们留下（J-1）/ J 是不是 - 这是预期的工作中，我们有
。
3. 的平等 O（日志（的sqrt（N））= 0（1/2 *的log（n）来自 O（日志（ N R个K））= O（K *的log（n））= O（日志（N））的任何常数 K 。（以你的情况下，K = 1/2）

1. The first sum is up to sqrt(i) since this is the point where j > (i / j).
2. The first sum is (j-1)/j for each j, because on average one out of j elements is getting into the break (1/3 of the elements are dividable by 3, 1/4 by 4,...) this leaves us (j-1)/j that are not - and this is the expected work we have.
3. The equality O(log(sqrt(n)) = O(1/2*log(n) comes from O(log(n^k))=O(k*log(n))=O(log(n)) for any constant k. (in your case k=1/2)

这篇关于如何解决大O符号为素数函数吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！