Я часто был слегка озадачен рекурсивными алгоритмами, которые, кажется, требуют магических скачков (с большой дозой сжатых обозначений, порожденных нехваткой чернил) логики.
Я понимаю, что альтернатива состоит в том, чтобы просто запомнить нотацию Big O для всех распространенных алгоритмов, но в определенный момент этот подход не дает результатов. Например, я рад раскрыть производительность для сортировки пузырьков, сортировки вставок, вставки / удаления двоичного дерева, сортировки слиянием и быстрой сортировки, но не прошу меня придумать производительность деревьев AVL или алгоритма кратчайшего пути Джикстры сверху. моей головы.
Куда мне обратиться:
- Обсуждение анализа рекурсивного алгоритма, использующего слова вместо множества символов
- Практикуйте проблемы, чтобы подтвердить, что мое недавно полученное понимание действительно правильно
Пример:
Bad:
Сигма V e T (1 + CV)
Возможный «хороший» эквивалент:
Объем работы, необходимый для 1 узла в дереве (1 + число дочерних узлов), который затем выполняется один раз для каждого элемента в дереве, где исходный узел является корнем.
Дополнительный комментарий:
Я мог бы просто посмотреть видео для каждого отдельного алгоритма, потому что нет никакого способа заставить свой голос превратиться в подстрочный индекс (или любое другое искажение), но я подозреваю, что это займет непомерное количество времени по сравнению с чтением текстовых описаний.
Обновление:
Вот 1 источник решенных проблем: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/ (это относится к пункту 2 выше)