这个纵横交错的程序的时间复杂度。这是要打印N个质数

我想知道如何计算该程序的TIME复杂度,外循环中的10定义了要打印的素数。您可以假设它为N。现在,它将打印10个质数。

#include <iostream>

using namespace std;

int main()
{   int number=2;
    bool flg=0;
    cout<<2<<"\t";
    number=3;
    for(int count=1;count<10;number+=2){
        for(int j = 3;j<(number/2);j+=2){
            if(number%j==0){
                flg=1;
                break;
            }    
        }
        if(flg==0)
            {cout<<number<<"\t";count++;}
        else
            flg=0;
    }
    return 0;
}
wcxoneper 回答:这个纵横交错的程序的时间复杂度。这是要打印N个质数

假设整数运算被视为恒定时间,而忽略了实际C ++整数的有限范围:

由于质数定理,外循环将迭代Theta(N ln(N))次。

几乎所有这些迭代都是针对非素数的,因为(奇数)自然数中非素数的密度收敛于一个。

非素数m的内部循环需要Theta(m)时间。

因此,该算法的时间复杂度总计为Theta(N^2 ln(N))

本文链接:https://www.f2er.com/3085821.html

大家都在问