Как мне найти сложность пространства и времени для этого кода
fun root(n) =
if n>0 then
let
val x = root(n div 4);
in
if (2*x+1)*(2*x+1) > n then 2*x
else 2*x+1
end
else 0;
fun isPrime(n,c) =
if c<=root(n) then
if n mod c = 0 then false
else isPrime(n,c+1)
else true;
Временная сложность функции root(n) здесь равна O(log(n)): число делится на 4 на каждом шаге, а код в самой функции равен O(1). Временная сложность функции isPrime равна o(sqrt(n)), так как она итеративно выполняется от 1 до sqrt(n). Проблема, с которой я сталкиваюсь сейчас, заключается в том, каков будет порядок обеих функций вместе? Будет ли это просто O(sqrt(n)) или O(sqrt(n)*log(n)) или что-то еще?
Я новичок в большой нотации O в целом, я просмотрел несколько веб-сайтов и видео на YouTube, пытаясь понять концепцию, но я не могу с уверенностью ее рассчитать... Если бы вы, ребята, могли указать мне на несколько ресурсов чтобы помочь мне попрактиковаться в расчетах, это было бы большим подспорьем.
@SimonShine да, спасибо, мне придется потратить немного больше времени на понимание основной теоремы, которая на первый взгляд выглядит очень полезной ... Не могли бы вы просто подтвердить, какой порядок будет для кода, который я опубликовал?
Ответы 1
root(n) равно O(log₄(n)), да.
isPrime(n,c) равно O((√n - c) · log₄(n)):
- Вы пересчитываете
root(n)на каждом этапе, даже если оно никогда не меняется, что приводит к «... · log₄(n)». - Вы повторяете
cот некоторого значения доroot(n); хотя он ограничен сверхуroot(n), он не ограничен снизу:cможет начинаться с 0, или с произвольно большого отрицательного числа, или с положительного числа, меньшего или равного √n, или с числа больше √n. Если вы предполагаете, чтоcначинается с 0, тоisPrime(n,c)равно O(√n · log₄(n)).
Вы, вероятно, захотите доказать это, используя либо индукцию, либо ссылку на основную теорему. Вы можете упростить isPrime, чтобы он не принимал c в качестве аргумента в своей внешней подписи и чтобы он не пересчитывал root(n) без необходимости на каждой итерации.
Например:
fun isPrime n =
let
val sq = root n
fun check c = c > sq orelse (n mod c <> 0 andalso check (c + 1))
in
check 2
end
Это isPrime(n) равно O(√n + log₄(n)) или просто O(√n), если мы опустим младшие члены.
Сначала он вычисляет root n один раз за O(log₄(n)).
Затем он зацикливается от 0 до root n один раз в O (√ n).
Обратите внимание, что ни один из нас формально ничего не доказал на данный момент.
(Правка: изменено check (n, 0) на check (n, 2), т.к.)
(Редактировать: удалено n как аргумент из check, поскольку оно никогда не меняется.)
(Правка: как вы заметили, Ариан, цикл от 2 до root n действительно равен O(√n), хотя вычисление root n занимает только O(log₄(n))!)
Я оставил c как есть, потому что на самом деле использую его как вспомогательную функцию в более крупном алгоритме. Мне очень нравится ваша реализация проверки, хотя спасибо вам за это. Чего я не понимаю, так это того, что, хотя в моей функции isPrime я итерирую от 2 до root (n) (я инициализирую c до 2), так что не должно ли это занимать время O (root (n))?
Ах, похоже, вы могли бы использовать проверку с какого-то момента и выше. Умный. :-) Я думал только о плюсах и минусах для доказательства и вообще минимизации интерфейсов. Отвечая на ваш вопрос: да, должен. Но вы вызываете root(n) один раз в каждой итерации. Это сопоставимо с кодом C for (int i = 0; i < expensiveOperation(); i++) и for (int i = 0, max = expensiveOperation(); i < max; i++).
Правильно я вижу. Но все же в коде, который у вас есть, цикл от 0 до root (n) должен иметь сложность O (root (n)), не так ли?
Мой ответ как-то не соответствует этому? (Я исправил 0 в 2, это было ошибкой с моей стороны.) Если «root(n) равно O (log₄ (n))», то не должна ли функция, которая вызывает root(n), также иметь термин в своей временной сложности, который равен также O (log₄ (n))? Я не уверен, что ваши вопросы направлены на формулировку «root (n)» против «log₄ (n)».
Извините, это похоже на недоразумение... Ваша функция isPrime должна иметь порядок O(√n), не так ли? Потому что он повторяется от 2 до √n? Согласно тому, что я изучал до сих пор, O (log n) можно игнорировать, потому что √n > log n...
Совершенно верно, я тупица. :-) Я исправил это сейчас. И да, вы можете легко исключить члены более низкого порядка, указав определение O (...) и выбрав большую константу, после чего член более высокого порядка будет всегда доминировать над термином (ами) более низкого порядка. Хотя это верно асимптотически, это также может быть немного непрозрачным: асимптотически это может ничего не изменить, полностью рекурсируете ли вы структуру данных один или три раза, но на практике для достаточно больших структур данных константы, кратные, безусловно, имеют значение.
Хорошо! Думаю, теперь я понимаю это гораздо лучше. Большое спасибо за помощь!
Отвечает ли это на ваш вопрос? Большое О рекурсивных методов