Какова сложность простого алгоритма?

Question

Я хотел бы знать, какова сложность этого алгоритма. N> = 3 целое число в качестве импульса. Спасибо!

initialisation : i=2
LOOP:
if N%i==0
     return 1; 
if i == [sqrt(N)]
     return 0; 
i= i + 1;

Answer 1

initialisation : i=2
LOOP:
if N%i==0
     return 1;       # 1 <-----
if i == [sqrt(N)]
     return 0;       # 2 <-----
i= i + 1;

Случай 1: N четное. Тогда мы закончим в O(1) - см. Строку (# 1). Или N нечетное и не простое. Тогда мы закончим, когда мы дойдем до некоторого делителя N (это произойдет до квадратного корня или одновременно).

Случай 2: N простое число. Затем мы нажмем [ n^0.5 ] чисел (см. Строку # 2) перед завершением.

Однако, как @Lutzl указывает в своем комментарии, точный расчет может учитывать время выполнения задействованного деления . Это немного некорректно, так как мы не знаем, какие алгоритмы умножения и деления используются. Но общее время выполнения будет O(max{a * sqrt(N), sqrt(N)}), где O(a) - время выполнения проверки N % i == 0. Здесь я предполагаю, что фактическое вычисление квадратного корня фактически является постоянным временем и выполняется только один раз, поэтому O(n^0.5) потому, что именно столько итераций вы получите, прежде чем алгоритм завершится для простого ввода.