Шаг 35.
Рекурсия на Python. Анализ времени выполнения рекурсивных алгоритмов. Предварительные математические соглашения. Пределы и правило Лопиталя

    На этом шаге мы напомним, что такое предел, и для чего используется правило Лапиталя.

    Стоимость вычисления различных алгоритмов можно сравнить с помощью предела отношения функций. Прежде всего 

  k/∞ = 0, ∞/k = ∞    ,
где k - константа, а символ ∞ следует понимать как значение предела. Кроме того, так как функции оценки стоимости вычислений, вообще говоря, возрастают (за исключением констант), их предел стремится к бесконечности при стремлении к бесконечности их аргументов. Например: 
  lim logbn = ∞ или lim na = ∞
  n→∞               n→∞
при допустимом основании логарифма b и a > 0. Поэтому зачастую при сравнении стоимости вычислений алгоритмов может возникнуть неопределённость вида 
  lim f(n)/g(n) = ∞/∞
  n→∞

    Обычно она разрешается упрощением дроби f(n)/g(n), пока не появится возможность получить отличный от неопределённости результат. Известный способ упрощения дроби - применение правила Лопиталя: 

  lim f(n)/g(n) = lim f'(n)/g'(n)      (3.3)
  n→∞             n→∞
где f'(n) и g'(n) - производные f(n) и g(n) соответственно. Формально правило Лопиталя верно только тогда, когда существует предел в правой части (3.3), что обычно имеет место.

    На следующем шаге мы рассмотрим суммы и произведения.




Предыдущий шаг Содержание Следующий шаг