c++ - 对于输入,C++ 查找用于查找输入是否为素数的算法的运行时间

  显示原文与译文双语对照的内容
61 5

这是我寻找质数的函数

void print(int num)
{
 for(int i=2; i<num/2; i++)
 {
 if(num%i==0)
 {
 cout<<"not primen";
 exit(0);
 }
 }
 cout<<"primen"; 
}

我在数字中输入。我正在试图用大的哦找到运行时。我记得找到运行时间跟日志有关系。

最糟糕的情况是我的程序将运行n/2 -1时间?

时间:原作者:0个回答

81 2

是的,循环运行n/for时间,并且只包含复杂性命令,所以运行时缩放为 a* ( n/2-1 ) 。在 Big-O 中,这是写为( n/2-1 ),因为常量因子不重要,这等于 O(n) 。

( 另一方面:它实际上是 theta(n),这意味着它不仅仅是从上到下),也是从下面的n

原作者:
...