查找我的算法的运行时间，以查找输入在输入方面是否是素数

Question

这是我查找素数的函数

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 次？

Answer 1

是的，循环运行 n/2-1 次，并且只包含恒定复杂性的命令，因此您的运行时在某些 a 中扩展为 a*（n/2-1）。在 big-o 中，这写为 O（n/2-1），因为常数因子无关紧要，所以它等于 O（n）。

（

顺便说一句：它实际上是theta（n），这意味着它不仅从上面被n包围，而且从下面被n包围）