#algorithm #recursion #time-complexity
#алгоритм #рекурсия #временная сложность
Вопрос:
Доброе утро, я изучаю алгоритмы и способ вычисления сложности при выполнении рекурсивных вызовов, но я не могу найти ссылку на то, как ограничение уровня в рекурсивных вызовах может повлиять на вычисление сложности. Например, этот код:
countFamilyMembers(int level,....,int count){
if(noOperationCondition) { // for example no need to process this item because business rules like member already counted
return count;
} else if(level >= MAX_LEVEL) { // Level validation, we want just to look up to certain level
return count //last level to see then no more recurrence.
} else {
for (...each memberRelatives...) { //can be a database lookup for relatives to explore
count = countFamilyMembers( level,..., count);
}
return count;
}
}
Я думаю, что это O (2 ^ n), потому что рекурсивный вызов в цикле. Однако у меня есть два основных вопроса:
1. Что произойдет, если значения цикла вообще не связаны с исходным вводом? это тоже можно считать «n»?
2. Проверка уровня наверняка сокращает количество рекурсивных вызовов, как это влияет на вычисление сложности?
Комментарии:
1. Один из подходов заключается в попытке развернуть рекурсию в цикл (в данном случае выглядит довольно просто). Затем вы можете оценить сложность нерекурсивного алгоритма, что часто проще сделать.
2. Что такое n с точки зрения ваших исходных входных параметров? Является ли MAX_LEVEL константой? Является ли разветвление (количество родственников из данного узла) ограниченным, или другой переменной, или чем-то еще? Это серьезно влияет на сложность.
3. n относится к числу родственников каждого человека. MAX_LEVEL является константой, я думаю, это должно значительно снизить сложность или, по крайней мере, сложность записи в терминах этого, я пока не уверен, как. Количество родственников для данного узла не ограничено, оно может быть любым значением, как в реальной жизни.
Ответ №1:
Спасибо за разъяснения. Итак, мы возьмем n в качестве некоторого «наилучшего показателя» по количеству родственников; в некоторых парадигмах это также известно как «разветвление».
Таким образом, у вас будет 1 человек на уровне 0, n на уровне 1, n ^ 2 на уровне 2 и так далее. Грубая оценка возвращаемого значения… и количество операций (посещений узла, приращений и т.д.) является суммой n ^level для уровней в диапазоне от 0 до MAX_LEVEL. Доминирующим членом является наивысший показатель, n ^ MAX_LEVEL.
С учетом приведенной информации я полагаю, что это ваш ответ: O (n ^^ MAX_LEVEL), он же полиномиальное время.
Обратите внимание, что, если вам случайно задано значение для n, даже верхняя граница для n, тогда это становится константой, и сложность равна O (1).
Комментарии:
1. большое вам спасибо! Я действительно ценю простоту ответа с точки зрения уровней, очень хорошо объясненный и понятный! Не могли бы вы, пожалуйста, просто уточнить последнюю строку о постоянном времени? Если n имеет верхнюю границу, не будет ли все равно повторяться n раз для каждого уровня, а затем n раз для каждого из родственников?
2. Предположим, что MAX_LEVEL равен 5, а n ограничено 10. Теперь у вас есть строгая верхняя граница 10^5 10^4 … 10^0 проверки. Это 111 111 проверок. Любая постоянная граница дает вам O(1) сложность. Конечно, это может завершиться за меньшее время, но вы исключили параметры как неограниченный фактор времени выполнения. Да, вы можете в некоторой степени предсказать это меньшее время выполнения, масштабируя с фактическим значением n , но в теории сложности это просто детали «субпостоянного времени».