Время Сложность этой функции проверки простоты

Question

Какова будет временная сложность этой функции

bool prime(int n) {
    if(n <= 1) {
        return false;
    } else if(n <= 3) {
        return true;
    } else if(n % 2 == 0 || n % 3 == 0) {
        return false;
    } else {
        for(int i = 5; i * i <= n; i += 6) {
            if(n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
    }
    return true;
}

Если бы мне пришлось угадывать, это было бы

O(sqrt(log(n)))

Answer 1

Каждое if является постоянным временем.

for l oop выполняется до тех пор, пока i * i не достигнет n, это означает, что он выполняется sqrt(n) / 6 раз. Таким образом, сложность составляет O(sqrt(n)).

Это не означает, что плотность простых чисел пропорциональна 1/log(n) (вероятно, это источник log(n) в вашем решении.

Обратите внимание, что временная сложность (без прилагательного) обычно рассматривается как наихудшая временная сложность:

Временная сложность - Википедия

Поскольку время работы алгоритма может различаться для разных входов того же размера, обычно считается сложность времени наихудшего случая , то есть максимальное количество времени, необходимое для входных данных заданного размера. Менее распространенным и обычно указываемым явно является среднее - сложность случая

В этом случае вычислить среднюю временную сложность намного сложнее.Вам нужно будет доказать, насколько быстро l oop завершается в среднем, когда n не является простым числом.