如何计算循环中有一个扩展数组(它本身是循环的)的算法的运行时间

Question

我有一个算法，可以在N下找到素数列表，以及所有N的最低因子。

/*
arrLF stands for arrLowestFactor, it stores all the LF
arrPrime is the list of primes under N. The variable pn is used to keep track of how many primes we have discovered. Initially pn is zero.
*/
for(int i = 2; i <= N; i++){
//if a number i hasn't got its lowest factor yet, it means we have discovered a new prime number. And this prime number will be the LF of i too.
if(!arrLF[i]){
arrPrime[pn++] = i;
arrLF[i] = i;
} 
//run through the list of prime once and fill up the lowest factor of (i * arrPrime[j]) in the arrLF table 
//it's like doing sieve of eratosthenes but we build the table up one at a time
for(int j = 1; i * arrPrime[j] <= N; j++){
arrLF[ i * arrPrime[j] ] = arrPrime[j];
if( i % arrPrime[j] == 0)
break;
}
}

对于外循环，它以O(N)运行。所以这个算法的运行将是O(N*M)，其中M是内部循环的运行时间。但既然素数的列表在不合理地扩展，我该如何评估M的复杂性？

顺便说一句，我是通过研究codeforce上一个红色编码器的解决方案找到这个算法的，有人知道这个算法或它的名字吗？

Answer 1

您的算法将在O(n)中运行。让我解释一下的原因

我们需要观察内部循环，以了解为什么它不会以指数方式影响时间复杂性。

在最坏的情况下，内部循环外观将为每次迭代运行以下时间

第一次迭代：1/2*N次

第二次迭代：1/3*N次

第三次迭代：1/4*N次

等等

因此，每次运行内部循环的次数都在减少。

我们可以说内部循环运行的总次数是SUM(1/2+1/3+1/4+…1/N)

这叫做谐波级数https://en.wikipedia.org/wiki/Harmonic_series_(数学)

尽管这个级数收敛到无穷大，但它收敛得非常慢，对于N为10^43，它小于100

所以实际上，在最坏的情况下，内部循环将运行N次，比如说，对于java浮点限制，最大运行100次

这意味着整个算法的时间复杂度就是内循环的时间复杂程度，因为外循环不运行任何其他循环。因此，时间复杂度将是O(Xn)，其中X是常数，正如我们所解释的，在java的数字限制内实际不会超过100或200，这意味着算法的总复杂度是O(n)，因为我们省略了常数