找到我的算法的运行时间，用于根据输入来查找输入是否是素数 [英] finding the running time for my algorithm for finding whether an input is prime in terms of the input

问题描述

这是我查找素数的函数。

This is my function for finding prime numbers

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

我试图找到运行时使用大哦。我记得找到运行时间与日志有关。

My input in num. I'm trying to find the runtime using big oh. I remember that finding the run time had something to do with log.

最糟糕的情况是我的程序运行n / 2 -1次。

The worst case would be that my program would run the n/2 -1 times?

推荐答案

是的，循环运行n / 2-1次，并且只包含常量复杂度的命令，所以你的运行时刻度为*（n / 2-1）为一些。在big-o中，这被写为O（n / 2-1），并且因为常数因子不重要，这等于O（n）。

Yes, the loop runs n/2-1 times and only contains commands of constant complexity, so your runtime scales as a*(n/2-1) for some a. In big-o this is written as O(n/2-1) and because constant factors don't matter this is equal to O(n).

an aside：它实际上是theta（n），这意味着它不仅从上面由n限制，而且从下面由n限制）

(as an aside: it is actually theta(n) which means, that it is not just bounded from above by n but also from below by n)

这篇关于找到我的算法的运行时间，用于根据输入来查找输入是否是素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！