c# - 如何解决素数函数的Big-O Notation？

Question

我正在尝试理解大 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 algorithm scales to huge problems. Whenever N doubles, the running time more (but not much more) than doubles.

虽然这似乎很好地描述了此代码片段的运行方式，但这是否意味着它是 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) ( The harmonic number ) 在 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)) 。根据this forum thread ，平方根之和在 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)