#algorithm #recursion #time-complexity
#алгоритм #рекурсия #временная сложность
Вопрос:
У меня есть сетка с x-сторонним полем в ней. Каждое поле содержит ссылку на x окружающих его полей. [x является постоянным]
У меня есть алгоритм, который реализован в этой области, (который, вероятно, может быть оптимизирован):
[псевдокод, подобный Java]
public ArrayList getAllFields(ArrayList list) {
list.addToList(this);
for each side {
if ( ! list.contains(neighbour) amp;amp; constantTimeConditionsAreMet()) {
neighbour.getAllFields(list) //Recursive call
}
}
return list;
}
У меня возникли проблемы с определением временной сложности.
ArrayList#contains(Object)
выполняется за линейное времяКак мне определить временную сложность? Мой подход заключается в следующем:
T(n) = O(1) T(n-1)
c(nbOfFieldsInArray - n) [The time to check the ever filling ArrayList]
T(n) = O(1) T(n-1) c*nbOfFieldsInArray - cn
Дает ли это мне T(n) = T(n-1) O(n)
?
Комментарии:
1. Где должен произойти рекурсивный вызов? Означает ли ‘getContinent’ быть ‘getAllFields’?
2. Я вставил комментарий в код 🙂
3. Измените список на хэш-таблицу, и у вас будет алгоритм O (n), где n = количество полей 🙂
4. Я планировал это сделать. Согласны ли вы, что алгоритм теперь равен O (n ^ 2)?
Ответ №1:
Комментарий, который вы добавили к своему коду, бесполезен. Что getContinent
делает?
В любом случае, поскольку вы используете линейный поиск ( ArrayList.contains
) для каждого потенциального добавления в список, то, похоже, сложность будет равна Omega (n ^ 2).
Комментарии:
1. Очень жаль, я назвал его по-другому раньше, я забыл, что переименовал его позже, и спасибо; Это уже подсказка 🙂
2. 1: Но придираться: «по крайней мере, O (n ^ 2)» не слишком осмысленно. Возможно, вы хотите сказать Omega (n ^ 2)?
3. @Moron: отмечено. Хотя мое прочтение en.wikipedia.org/wiki / … указывает, что «Omega (n ^ 2)» означает «O больше, чем n ^ 2», что (я думал) было таким же, как «по крайней мере, O (n ^ 2)». Однако я вижу, что мой термин менее информативен.
4. @JIm: Это не «менее информативно». Технически говоря, это фактически бессмысленно.
5. Для большей ясности: O (n ^ 2) означает не хуже, чем cn ^ 2: т.е. BigOh используется для определения верхних границ. Итак, то, что вы говорите, «по крайней мере, не хуже, чем cn ^ 2». Omega используется для определения нижних границ, что является именно тем, что вам здесь нужно…
Ответ №2:
Ваше повторение кажется правильным T(n) = T(n-1) theta(1)
.
Если вы нарисуете дерево рекурсии, вы заметите, что у вас есть единственная ветвь со значениями theta(n-1), theta(n-2), ..., theta(2), theta(1)
, если вы сложите все уровни, вы получите арифметический ряд 1 2 3 … n
S1 = 1 2 3 ... n
Если вы определяете
S2 = n ... 3 2 1
а затем вычислите S1 S2
, вы получите
S1 S2 = 2*S1 = (n 1) (n 1) ... (n 1) = n(n 1)
поэтому
2*S1 = n(n-1) => S1 = n(n-1)/2
что означает T(n) = 1/2 theta(n(n-1)) = 1/2 theta(n^2) = theta(n^2)