Простое решение распространенных рецидивов

Вам было сложно решить временную сложность повторяющихся отношений? Я покажу вам, как быстро и легко решить некоторые из наиболее распространенных повторяющихся соотношений, не используя никаких других методов, кроме запоминания.

Ниже приведены наиболее часто встречающиеся случаи.

Примечание. a, b, d и k - постоянные значения.

  1. T(n) = T(n-1)+b, T(1) = a
    T(n) = O(n)
  2. T(n) = T(n-1) + bn, T(1) = a
    T(n) = O(n²)
  3. T (n) = T (n / 2) + b, T (1) = a
    T (n) = O (журнал n)
  4. T(n) = T(n/2) + bn, T(1) = a
    T(n) = O(n)
  5. T(n) = kT(n/k) + b, T(1) = a
    T(n) = O(n)
  6. T (n) = kT (n / k) + bn, T (1) = a
    T (n) = O (n log n)
  7. T(n) = T(n-1) + T(n-2) + d, T(1) = a, T(2) = b
    T(n) = O(2^n)
  8. T(n) = T(n-1) + b n^k, T(1) = a
    T(n) = O(n^(k+1))

Если вы хотите узнать больше об Анализ алгоритмов, вы можете пройти мой онлайн-курс здесь. У меня также есть курс на Udemy.com под названием Recurrence Relation Made Easy, где я помогаю студентам понять, как решать повторяющиеся отношения и асимптотические термины, такие как Big-O, Big Omega и Theta. Вы можете посмотреть мой канал на YouTube с видео, где я решаю рекуррентные отношения и выполняю анализ алгоритмов кода, который любой может проверить бесплатно!



Введение в анализ алгоритмов [для начинающих]
Понимание и решение алгоритмов с использованием временной сложности Big O, Big Omega и Theta. www.udemy.com





Упрощение отношений повторяемости | Udemy
Руководство по решению любой программы рекурсии или отношения повторения. www.udemy.com



Спасибо за прочтение этой статьи, надеюсь, она будет вам полезна! Продолжайте учиться, и если вы хотите больше видео по информатике, программированию и анализу алгоритмов, посетите и подпишитесь на мои каналы YouTube (randerson112358 и compsci112358)

Ознакомьтесь со следующими материалами / видео по информатике, анализу алгоритмов, программированию и логике:

Канал YouTube:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Веб-сайт:
http://everythingcomputerscience.com/

Видеоуроки по взаимосвязи повторяемости:
https://www.udemy.com/recurrence-relation-made-easy/

Видеоурок по анализу алгоритмов:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

"YouTube канал:"

Веб-сайт по информатике:

Видео Udemy по алгоритмическому анализу:

Ресурсы:
http://www.cs.cornell.edu/courses/cs211/2005sp/Lectures/L14-BigO/L14-15-Complexity.4up.pdf