O素数函数的符号？

2018-06-14 01:28:18

我正在尝试了解Big-O符号。非常抱歉，如果我问的东西太明显了，但我似乎无法绕过这一点。

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

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);
     }

现在到目前为止，我认为两个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的定义

Linearithmic算法扩展到巨大的问题。每当N翻倍时，运行时间比双打多（但不会多）。

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

@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)) 。根据这个论坛线程，平方根的和在O(n*sqrt(n)) ，这比O(nlogn) “更糟”。

注意事项：

第一个和高达sqrt（i），因为这是j > (i / j) 。

第一个和是每个j (j-1)/j ，因为j元素平均有一个进入到中断点（三分之一的元素可以被3,1 / 4除以4 ...）这让我们(j-1)/j不是 - 这是我们所期望的工作。

等式O(log(sqrt(n)) = O(1/2*log(n)来自O(log(n^k))=O(k*log(n))=O(log(n))对于任何常数k （在你的情况k = 1/2）

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

当i处于区间[2, 3]时，内部循环不会迭代。

当i处于区间[4, 8]时，内部循环会迭代一次。

当i处于区间[9, 15]时，内部循环会迭代两次。

当i处于区间[16, 24]时，内部循环会重复三次。

当i处于区间[25, 35]时，内部循环会重复四次。

当i处于区间[36, 48]时，内部循环会重复五次。

当i处于区间[49, 63]时，内部循环会重复6次。

当i处于区间[64, 80]时，内部循环会重复执行7次。

当i处于区间[81, 99]时，内部循环会重复8次。为了验证上述情况，我必须去一个大于100的范围。

当i处于区间[100, 120]时，内部循环会重复9次。

依赖于i's价值的区间可以表示如下：

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

因此，我们可以这样做：

经验证明：

在这里输入图像描述

通过一个有用的WolframAlpha链接：

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

形式上，我们可以陈述如下：

在这里输入图像描述

我看着你的代码 - 并没有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 / ln n个数字是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变得非常大的时候显示结果的常量因子非常大。

链接地址: http://www.djcxy.com/p/40039.html

上一篇: O Notation for prime number function?

下一篇: Why is the Fibonacci Sequence Big O(2^n) instead of O(logn)?