предисловие
Рекурсия — очень важная концепция, которую я также люблю тестировать в интервью. Потому что он может не только проверять навыки алгоритма программиста, но и проверять правильностьвременная и пространственная сложностьпонимания и анализа.
В этой статье рассматривается только один вопрос, который также является первым вопросом о рекурсии почти во всех книгах по алгоритмам, но я стараюсь говорить о цветах Здесь я разделяю четыре разных точки зрения, чтобы вы могли получить разные выгоды.
- временная сложностьподробный анализ
- идентифицировать иупрощатьв рекурсивном процессеповторениеоперация
- волк в овечьей шкуре
- Демонстрация своих навыков надлежащим образом помогла мне получить мою первую работу
Идеи алгоритма
Всем известно, что метод, вызывающий сам себя, является рекурсивным, да, но это лишь самое поверхностное понимание рекурсии.
затем рекурсивныйвеществочто это?
отвечать:Суть рекурсии в том, чтобы иметь возможность разложить большую проблему на более мелкие, а затем мы можем использовать решение маленькой проблемы для построения решения большой проблемы.
Как вы нашли решение этой маленькой проблемы?
A: Он построен из решения задачи с меньшим размером.Когда задача слишком мала, чтобы быть меньше, это время, когда достигается задача с нулевым размером, что является базовым случаем.
Итак, резюмируя три шага рекурсии:
Base case: Это проблема рекурсии с нулевым числом, а также конечная точка рекурсии. Когда вы достигаете наименьшей проблемы, вы можете напрямую дать результат, вам не нужно идти дальше, иначе он станет бесконечный цикл;
демонтаж: задача каждого слоя должна быть меньше, чем проблема предыдущего слоя, и размер задачи можно непрерывно уменьшать, чтобы достичь базового случая от большого к меньшему;
комбинация: Получите решение маленькой проблемы, но также знайте, как сконструировать решение большой проблемы.
Поэтому для каждой рекурсивной проблемы мы анализируем ее по этим трем шагам, и если эти три проблемы прояснены, код легко пишется.
Последовательность Фибоначчи
Хотя этот вопрос является банальным, я считаю, что то, чем я здесь делюсь, определенно принесет вам другие преимущества.
Описание темы
Последовательность Фибоначчи итальянский математик.Он не имеет никакого отношения к изучению процесса размножения кроликов.Проведя исследования, он обнаружил, что ее можно записать в виде такой последовательности: 1, 1, 2, 3, 5, 8, 13, 21 …то есть каждое число равно сумме двух предшествующих ему чисел. Затем дайте вам n-е число и спросите, что такое F(n).
Разобрать
Это легко выразить математически:
Код также очень прост и состоит из трех шагов, которые мы только что описали:
- base case: f(0) = 0, f(1) = 1.
- Разложение: f(n-1), f(n-2)
- Комбинация: f(n) = f(n-1) + f(n-2)
Затем выпишите это:
class Solution {
public int fib(int N) {
if (N == 0) {
return 0;
} else if (N == 1) {
return 1;
}
return fib(N-1) + fib(N-2);
}
}
Но скорость, которую дает это решение, Leetcode только быстрее, чем ответ 15%, потому что его временная сложность слишком высока!
Анализ процесса
Это первое, чем я хочу поделиться, как анализировать рекурсивный процесс.
Сначала мы рисуем это дерево рекурсии, например, мы рисуем дерево рекурсии F(5):
Каков фактический маршрут выполнения?
Первый — следовать по крайней левой строке до конца: F(5) → F(4) → F(3) → F(2) → F(1), наконец, есть базовый случай, который может вернуть F (1) = 1, затем вернитесь на уровень F(2), спуститесь еще ниже, то есть F(0), снова достигните дна, вернитесь к F(2) и получите F(2) = 1+0 = 1 В результате верните этот результат в F(3), затем в F(1), получите результат и затем вернитесь в F(3), чтобы получить F(3) = left + right = 2, а затем верните этот результат .. .
Этот способ в основном выполняется нашим компьютеромСистема фон Нейманасоздан, в настоящее времяОдин ЦП и одно ядро могут одновременно выполнять только одну инструкцию., поэтому F(3) и F(4) не могут выполняться вместе.F(4) должна выполняться первой (этот код ставит fib(N-1) впереди), а затем выполнять F(3).
Когда мы отлаживаем в IDE, мы можем видеть ситуацию в стеке: это действительно самая левая строка, которая идет первой, всего 5 слоев, а затем возвращает слой за слоем.
Для тех, кто не понимает, вы можете перейти на станцию B или YouTube, чтобы посмотреть видео-объяснение, просто введите Tian Xiaoqi~
анализ временной сложности
Как оценить качество алгоритма?
Многие проблемы имеют несколько решений, ведь все дороги ведут в Рим. Но как оценить плюсы и минусы каждого метода, мы обычно используемВыражения с большим Оизмерятьвремя и местосложность.
Временная сложность: по мере роста независимой переменной увеличивается требуемое время.
Здесь Big O означает, что алгоритмworst caseпроизводительность, это то, что нас больше всего беспокоит, иначе система не может удержаться, когда билет на Весенний фестиваль захватывается, скажите, этот алгоритм очень хорош?
Конечно, есть и другие способы измерения времени и пространства, такие как
Тета: описывает тесную связь
Omega(n): Это описывает лучший случай, лучший случай, бессмысленный
Это также дало нам немного вдохновения, не говорите, как хорошо вы обычно работаете, это бессмысленно; интервью измеряет ваш уровень в худшем случае; не говорите, что интервью не показало ваш истинный уровень, суть в том, что это это наш истинный уровень.
Так какова временная сложность этой задачи?
Ответ: Поскольку мы проходим через каждый узел, мы кладемСкладываем время всех узловэто общее время.
Здесь то, что мы делаем в каждом узле, — это сложение и суммирование, что является операцией O (1), и время для каждого узла одинаково, поэтому:
总时间 = 节点个数 * 每个节点的时间
это становится запросом节点个数математическая задача:
При N = 5,
Верхний слой имеет 1 узел,
2 на втором этаже,
4 на третьем этаже,
8 на четвертом этаже,
16 на пятом этаже, представьте большое дерево, если его засыпать :)
Не беспокойтесь о незаполненном пространстве здесь, должно быть несколько отсутствующих узлов, но, как мы только что сказали о временной сложности большого выражения O, мы ищем наихудший случай.
Тогда общее количество узлов равно:
1 + 2 + 4 + 8 + 16
Это сумма пропорционального числового ряда.Конечно, для расчета можно использовать математические формулы, но есть и小技巧Может помочь вам быстро рассчитать:
На самом деле количество узлов в каждом предыдущем слое не будет превышать количество узлов в последнем слое.Общее количество узлов не превышает количество узлов в последнем слое * 2, и тогда во временной сложности большой O Постоянный член также не имеет значения, поэтому общая временная сложность равна:
Количество узлов в последнем слое: 2^n
анализ пространственной сложности
Пространственная сложность, написанная в общей книге, относится к:
требуется при работе алгоритмавсепространство памяти
Но это обычно используется в компании, а также задается на собеседовании.
Auxiliary space complexity:
требуется для запуска алгоритмадополнительныйкосмос.
Приведите пример, иллюстрирующий разницу: например, если результат позволяет вывести массив длины n, то это пространство O(n) не входит в пространственную сложность алгоритма, потому что это пространство нельзя экранировать, т.к. не до вас алгоритмический.
Как анализировать сложность пространства?
Мы только что говорили о системе фон Неймана, и из рисунка легко увидеть, что она最左边这条路线Занимает больше всего места в стеке, постоянно压栈, то есть от 5 до 4, от 3 до 2, пока не будет нажата 1, а затем возвращается базовый случай, сложность пространства, занимаемого каждым узлом, составляет O (1), поэтому общая сложность пространства равнаO(n).
Я также упомянул об этом в видео выше 👆, студенты, которые не понимают, посмотрите видео~
оптимизация
Тогда мы подумали, почему такая простая операция имеет экспоненциальную временную сложность? Что делает время таким большим.
Нетрудно заметить, что в этом деревеRecursion Tree, слишком много重复计算.
Например, здесь F(2) вычисляется 3 раза, а F(3) вычисляется 2 раза, и каждый раз его нужно вычислять заново.狗熊掰棒子Неужели это горькая слеза.
После нахождения причины, чтобы решить этот вид повторяющихся вычислений, метод, используемый компьютером, фактически такой же, как и у нас, людей:记笔记.
Почему для многих профессий, таких как врачи, юристы и инженеры, опыт более ценен? Поскольку мы многое видели и многое накопили, в следующий раз, когда мы столкнемся с похожей проблемой, мы сможем быстро дать решение.Даже если мы не сможем решить ее какое-то время, мы также избежим слепых проб и ошибок.站在过去的高度不断进步, вместо того, чтобы каждый раз начинать с нуля.
Вернемся к алгоритму оптимизации. Как компьютер делает заметки?
Если мы хотим найти F(n), нам нужно
记录 F(0) ~ F(n-1) 的值,
Затем выберите подходящую структуру данных для ее хранения.
Здесь очевидно, используйте массив для хранения:
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| F(n) | 0 | 1 | 1 | 2 | 3 | 5 |
С помощью этой шпаргалки мы можем получить результаты от начала до конца, так что каждая точка вычисляется только один раз и может быть записана с помощью цикла for, а код очень прост.
class Solution {
public int fib(int N) {
if (N == 0) {
return 0;
}
if (N== 1) {
return 1;
}
int[] notes = new int[N+1];
notes[0] = 0;
notes[1] = 1;
for(int i = 2; i <= N; i++) {
notes[i] = notes[i-1] + notes[i-2];
}
return notes[N];
}
}
Эта скорость 100%~
Но мы видим, что в пространстве должно быть пространство для оптимизации.
Подумайте об этом, мы на самом деле记笔记的时候需要记录这么多吗? Нужно вести заметки от детского сада до начальной школы, от средней школы до средней школы?
Фактически каждый расчет只取决于它前面的两项, так что просто оставьте эти два.
Затем мы можем использовать массив длины 2 для вычисления или просто использовать 2 переменные.
Код обновления:
class Solution {
public int fib(int N) {
int a = 0;
int b = 1;
if(N == 0) {
return a;
}
if(N == 1) {
return b;
}
for(int i = 2; i <= N; i++) {
int tmp = a + b;
a = b;
b = tmp;
}
return b;
}
}
Таким образом, мы оптимизируем сложность пространства дляO(1), временная сложность такая же, как при использовании записи массиваO(n).
Этот метод на самом деле动态规划 Dynamic Programming, код написан очень просто.
Тогда давайте сравним рекурсию и DP:
RecursionЭто от большого к меньшему, разложенному слой за слоем, пока базовый случай не может быть разложен, а затем объединен и возвращен;
DPЭто от детства до взрослой жизни, делать хорошие заметки и постоянно прогрессировать.
этоRecursion + Cache = DP
Как записать эту заметку, как эффективно делать заметки, в этом сложность DP.
Некоторые люди говорят, что DP обменивает пространство на время, но я так не думаю, и этот вопрос является хорошим примером.
При решении задачи с рекурсией мы видим, что в стеке есть место O(n), ноС помощью DP мы можем оптимизировать пространство до O(1), а DP может выполнить двойную оптимизацию времени и пространства.
На самом деле последовательность Фибоначчи имеет множество применений в реальной жизни.
Например, в нашей компании и во многих крупных компаниях каждой задаче нужно давать баллы, 1 балл означает, что на выполнение уходит примерно 1 день, а тогда баллы только 1, 2, 3, 5 и 8. (Если их больше, чем Для задания на 8 баллов нужно разбить его на менее 8 баллов, чтобы каждый мог выполнить его в течение двух недель.)
Поскольку задачи никогда не могут быть выполнены, а время каждого ограничено, каждая группа соберется, выберет самые важные задачи для всех, а затем каждый подберет соответствующие задачи в соответствии со своими доступными днями.
Волк в козьей шкуре
Тогда некоторые студенты могут подумать, этот вопрос такой простой, это все в 2020 году, собеседование еще будет проходить тест?
отвечать:Действительно будет.
Просто не могу дать это вам таким простым способом.
такие как знаменитыйподниматься по лестницепроблема:
Лестница из N ступеней может подняться на один или два этажа за раз, сколько всего путей?
Подумайте об этом таким образом:
Находясь в текущей позиции, он может исходить только из предыдущего слоя или первых двух слоев, поэтому f (n) = f (n-1) + f (n-2).
Этот вопрос на самом деле был задан, когда я проходил собеседование тогда, когда я еще писал на Python, чтобы продемонстрировать свои навыки,Также использовал лямбда-функцию:
f = lambda n: 1 if n in (1, 2) else f(n-1) + f(n-2)
Временная сложность рекурсивного письма слишком высока, поэтому я написал версию с циклом for.
def fib(n)
a, b = 1, 1
for i in range(n-1):
a, b = b, a+b
return a
Затем я также написал метод кэширования:
def cache(f):
memo = {}
def helper(x):
if x not in memo:
memo[x] = f(x)
return memo[x]
return helper
@cache
def fibR(n):
if n==1 or n==2: return 1
return fibR(n-1) + fibR(n-2)
Кстати, я также поболтал с интервьюером о хвостовой рекурсии:
Хвостовая рекурсия Хвостовая рекурсия: рекурсивное предложение является последним предложением всего метода.
Так что же в этом особенного?
Особенность хвостовой рекурсии в том, что мы можемЕго легко преобразовать в итеративную запись, конечно, некоторые умные компиляторы сделают это за нас автоматически (не говоря уже о явном преобразовании, а для итеративного запуска во время выполнения, фактическое потребление памяти составляет O(1))
Так почему?
Поскольку при возврате откат не требуется, рекурсия является здесь последним шагом, и нет необходимости возвращаться на следующий уровень.
def fib(n, a=0, b=1):
if n==0: return a
if n==1: return b
return fib(n-1, b, a+b)
Наконец-то придумал свои козыри: лямбду и редукцию
fibRe = lambda n: reduce(lambda x, n: [x[1], x[0]+x[1]], range(n), [0, 1])
Увидев удовлетворенное выражение лица интервьюера, он продолжил углубленный разговор...
Так что не думайте, что это просто, один и тот же вопрос можно решить семью или восемью способами, проанализируйте преимущества и недостатки каждого метода, расширьте его там, где вы можете расширить его, и покажите свои твердые базовые навыки. твоё шоу. Навскидку, чтобы обмануть интервьюера~lol
Вот и все содержание этой статьи.Интересно, как вы себя чувствуете после ее прочтения? Дай мне знать, как ты себя чувствуешь~
Я сегодня давно сделал это видео.Если вам нравится эта форма, пожалуйста, сделайте три последовательных ссылки:
Нажмите, чтобы посмотреть, подбодрите меня!
Написание комментариев вслепую делает меня очень популярным!
Вперед вперед вперед вперед, люби ее, подари ей!
Для тех из вас, кто хочет увидеть больше проблем со структурами данных и алгоритмами со мной, помнитеПодписывайтесь на меня, я Тянь Сяоци, так работает алгоритм.