如何解决素数函数的Big-O表示法？

我想了解Big-O表示法。 很抱歉，如果我问的是太明显的东西，但我似乎无法解决这个问题。

我有以下C＃代码函数，我正在尝试计算Big-O表示法。

for (i = 2; i < 100; i++) { for (j = 2; j  (i / j)) Console.WriteLine("{0} is prime", i); } 

到目前为止我得到的是，我认为if子句被认为是常数O（1）并且在计算此算法时没有考虑到这一点？ 如果我已经正确理解了一个for循环

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

因为它是线性函数，所以O（n）和嵌套循环不依赖于来自周围循环的变量

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

是O（n ^ 2）？ 但是我如何计算一个函数，例如第二个循环依赖于第一个循环并创建非线性函数的顶部函数？

我发现了一个linearithmic的定义

线性算法可以扩展到巨大的问题。 每当N加倍时，运行时间会比双倍更多（但不会多）。

虽然这似乎是对这段代码片段如何运行的一个很好的描述，这意味着它是O（N Log [n]），如果是这样，我怎么能计算出来？

Answer 1

@Jon很接近，但他的分析有点不对， 算法的真正复杂性是O(n*sqrt(n)) 。

这是基于以下事实：对于每个数字i ，您应该在内循环中执行的“工作”的预期数量是：

 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(i) （ 谐波数 ）在O(log(sqrt(i)) = O(1/2*log(i) ，我们可以得出结论复杂度为O(sqrt(i)-log(i)) = O(sqrt(i)) ，每个素数计算。

由于每个i重复完成，因此问题的总复杂度为O(sqrt(2) + sqrt(3) + ... + sqrt(n)) 。 根据这个论坛post ，平方根的总和在O(n*sqrt(n)) ，这比O(nlogn) “更差”。

需要注意的事项：

1. 第一个总和最多为sqrt（i），因为这是j > (i / j) 。
2. 每个j的第一个和是(j-1)/j ，因为平均有一个j元素进入中断（1/3的元素可以分为3,1 / 4×4，……）这使得我们(j-1)/j不是 – 这是我们所期望的工作。
3. 等式O(log(sqrt(n)) = O(1/2*log(n)来自O(log(n^k))=O(k*log(n))=O(log(n))对于任何常数k 。（在你的情况下k = 1/2）

Answer 2

分析你的算法，我想出了以下内容：

• 当i在区间[2, 3]时，内部循环不会迭代。
• 当i在区间[4, 8]时，内循环会迭代一次 。
• 当i在区间[9, 15]时，内循环会迭代两次 。
• 当i在区间[16, 24]时，内循环会迭代三次 。
• 当i处于区间[25, 35]时，内循环会迭代四次 。
• 当i在区间[36, 48]时，内循环会迭代五次 。
• 当i在区间[49, 63]时，内循环会迭代六次 。
• 当i在区间[64, 80]时，内循环会迭代七次 。
• 当i在区间[81, 99]时，内循环会迭代八次 。 我不得不去超过100的范围来validation上述情况。
• 当i在区间[100, 120]时，内循环会迭代九次 。

取决于i's值的区间可以表示如下：

 [i^2, i * (i + 2)] 

因此，我们可以这样做：

经验validation：

使用有用的WolframAlpha链接：

 http://www.wolframalpha.com/input/?i=sum[+floor%28+i^%281%2F2%29%29+-+1+]+with+i+from+2+to+99. 

在forms上，我们可以陈述以下内容：

Answer 3

我查看了你的代码 – 而且没有n。 代码不依赖于任何n。 它将始终以完全相同的固定时间运行。 你可以计算它需要多长时间，但总是相同，恒定，时间。 如上所述，以“for（i = 2; i <100; ++ i）”开头的代码在O（1）中运行。

所以将第一行改为

 for (i = 2; i < n; ++i) 

现在我们的代码实际上取决于n。 内循环最多运行sqrt（i）次迭代，小于sqrt（n）。 外循环运行大约n次迭代。 因此执行时间最多为O（n sqrt（n））= O（n ^ 1.5）。

实际上，它会跑得更快。 它通常不会达到sqrt（i），但只有在找到i的除数之前。 一半的数字可以被2整除（一次迭代）。 其余三分之一可被3整除（两次迭代）。 其余五分之一可被5整除（四次迭代）。 关于n / nn个数是具有sqrt（n）次迭代的素数。 关于n / ln n个更多数是两个素数的乘积> n ^（1/3），最多迭代为sqrt（n）。 其余的迭代次数少于n ^（1/3）。

所以代码实际上以O（n ^ 1.5 / ln n）运行。 您可以通过使用最高为sqrt（n）的素数表来改进这一点，并且您将降至O（n ^ 1.5 / ln ^ 2 n）。

但实际上，你可以打赌，Console.WriteLine（）比检查一个数字是素数要花费更长的时间。 如果你坚持列出所有质数，那么你的算法将由O（n / ln n）时间控制，并且在显示结果之前有一个非常大的常数因子，直到n变得非常大。