Я делаю несколько вопросов на собеседовании и наткнулся на этот:
Учитывая список целых чисел, которые представляют высоты хеджирования, определите минимальное количество ходов, чтобы сделать хеджирование красивым - то есть , вычислите минимальное количество изменений, необходимых для чередования массива между увеличением и уменьшением. Например, [1,6,6,4,4] должен возвращать 2, так как вам нужно изменить вторые 6 на что-то> 6 и последние 4 на что-то <4. Предположим, что минимальная высота равна 1, а максимальная высота равна 9. Вы можете изменить любое число, которое находится в диапазоне от 1 до 9, и это считается как 1 перемещение независимо от разницы с текущим числом. </p>
Мое решение здесь: https://repl.it/@plusfuture / GrowlingOtherEquipment
Я пытаюсь выяснить время выполнения O для этого решения, которое является запомненной рекурсией. Я думаю, что это O(n^3), потому что для каждого индекса мне нужно проверить 3 возможных состояния для остальной части массива, changeUp, noChange и changeDown. Мой друг утверждает, что это O(n), так как я запоминаю большинство решений и покидаю ветки, где массив не "симпатичен" сразу.
Может кто-нибудь помочь мне понять, как анализировать среду выполнения для этого решения? Благодаря.