Сложность доказательства для рекурсивной функции

Я пытаюсь определить сложность этой функции, где D и element - целые числа, а list - это упорядоченный список целых чисел. Обратите внимание на то, что (otherElement-element) будет строго положительным.

def doFunc(element, D, list):
  x = 0 
  if(D > 0):
    for otherElement in list:
      if otherElement == element:
        x += 1
      if otherElement > element:
        return x + (doFunc (otherElement,D-(otherElement-element) , list))
  return x

Учитывая, что список не всегда будет полностью повторяться, я не знаю, как определить временную сложность для этой функции.


time-complexity big-o proof
person FranckN    schedule 26.03.2014    source источник
comment
См. stackoverflow.com/a/22615862/847269, где я отвечаю на вопрос, похожий на этот, но явно отличающийся от него. один.   -  person Patrick87    schedule 26.03.2014
comment
Пытался оптимизировать алгоритм. Видите ли, мне нужно решить задачу с временной сложностью, строго меньшей, чем O (n ^ 2), но я не совсем понимаю, как вычислить большое o. Я подумал, что добавление нового условия может помочь мне уменьшить сложность. Вы говорите мне, что это то же самое, что я писал раньше?   -  person FranckN    schedule 26.03.2014
comment
Нет; Я сейчас пишу ответ, но здесь сложность действительно лучше. Просто укажу, что это был аналогичный вопрос; извините, если это был ваш вопрос, и я вас не узнал :)   -  person Patrick87    schedule 26.03.2014
comment
нет проблем спасибо за помощь   -  person FranckN    schedule 26.03.2014

Ответы (1)


arrow_upward
1
arrow_downward

doFunc проверяет list слева направо, чтобы найти otherElement больше или равное предоставленному element. Выполняется не более одного рекурсивного вызова. Мы можем попытаться вычислить временную сложность этой функции для наихудшего случая, определив, какие входные данные должны быть наихудшими, и проанализировав поведение.

Предположим, мы начинаем со списка размером 1; назовите это {1}. Если мы вызовем функцию из этого списка, сколько итераций мы могли бы выйти из цикла for? Что ж, если мы установим element = 1, мы получим одну итерацию. Однако, если установлено element = 0, мы можем заставить doFunc рекурсивно вызывать себя с element = 1; это означает, что мы получаем две итерации. Убедите себя, что мы никогда не сможем выпустить более двух doFunc итераций для этого списка. Также убедитесь, что выбор {1} по сути не важен; любой одноэлементный список будет работать таким же образом.

Предположим теперь, что мы хотим найти список наихудшего случая длиной 2; должно ли следующее число быть таким же, большим или меньшим? Рассмотрим {1, 1}, {1, 2} и {1, 0}. Вызов doFunc с element = -1 вызовет не более 3, 5 и 3 итераций цикла for соответственно. Добавление большего элемента приводит к наихудшему поведению для списка длиной 2.

Убедите себя, что худший вариант - это возрастающий список чисел; фактически, из-за ограничивающего фактора D худший случай - это список формы {a, a+1, a+2, ..., a+n-1} из n элементов. Для такого списка мы имеем следующее поведение при установке element < a:

  1. Одна итерация при первоначальном вызове doFunc; тогда у нас есть otherElement > element, поэтому мы рекурсивно вызываем doFunc.
  2. Две итерации при первом рекурсивном вызове doFunc; тогда у нас есть otherElement > element, поэтому мы снова рекурсивно вызываем.
  3. Точно так же при k-м рекурсивном вызове doFunc мы должны ожидать k+1 итераций цикла for. Поскольку цикл for не может повторяться более n раз в контексте одного вызова, это означает, что у нас есть не более n - 1 рекурсивных вызовов doFunc.

У нас есть 1 + 2 + ... + n = O(n^2). Предполагается, что d > n. Предполагая d < n, мы не можем получить все рекурсивные вызовы; в этом случае у нас может быть не более 1 + 2 + ... + d итераций, или O(d^2). Следовательно, поведение этой функции в наихудшем случае - O(min(n^2, d^2)). Сложность вопроса в вашем другом вопросе была O(dn), что хуже, чем сложность здесь, за исключением d = n, и в этом случае производительность такая же.

РЕДАКТИРОВАТЬ: обратите внимание, что константы для временной сложности здесь практически гарантированно будут значительно лучше, чем для другой вашей попытки, поэтому вы увидите заметно лучшую производительность, несмотря на ту же асимптотическую сложность.

person Patrick87    schedule 26.03.2014