Я начинаю изучать вычислительную сложность, нотацию BigOh и тому подобное, и мне было поручено выполнить алгоритм целочисленной факторизации и определить его сложность. Я написал алгоритм, и он работает, но у меня проблемы с расчетом сложности. Псевдокод выглядит следующим образом:
DEF fact (INT n)
BEGIN
INT i
FOR (i -> 2 TO i <= n / i STEP 1)
DO
WHILE ((n MOD i) = 0)
DO
PRINT("%int X", i)
n -> n / i
DONE
DONE
IF (n > 1)
THEN
PRINT("%int", n)
END
То, что я пытался сделать, я считаю, крайне неверно:
f (x) = n-1 + n-1 + 1 + 1 = 2n
, поэтому
f (n) = O (n)
Что я считаю неправильным, потому что алгоритмы факторизации должны быть сложными в вычислительном отношении, они даже не могут быть полиномиальными. Так что вы предлагаете мне помочь? Может быть, я слишком устал в это время ночи, и я все лажаю: (
Заранее благодарю.