Временная сложность рекурсивного алгоритма

#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)