Временная Сложность Появления Кодекса - 2016 День 19
Задача Advent of Code Day 19 определена следующим образом:
Эльфы с номерами от 1 до N сидят в кругу. Каждый эльф приносит подарок. Затем, начиная с первого эльфа, они по очереди крадут все подарки от эльфа слева от них. Эльф без подарков удаляется из круга и не по очереди. Итак, если N = 5, то:
- Эльф 1 получает подарок Эльфа 2.
- Elf 2 не имеет подарков и пропускается
- Эльф 3 принимает подарок Эльфа 4.
- Elf 4 не имеет подарков и также пропускается.
- Эльф 5 получает два подарка Эльфа 1.
- Ни у Elf 1, ни у Elf 2 нет подарков, поэтому оба пропускаются.
- Эльф 3 получает три подарка Эльфа 5, заканчивая игру.
Кто заканчивает со всеми подарками для общего случая N?
После решения этих проблем мне всегда нравится смотреть на решения других, чтобы изучить некоторые новые уловки. Одним из тех решений, которые я прочитал, было решение Питера Норвига здесь, и я заметил, что он упоминает об удалении из списка для каждого эльфа, чьи подарки взяты, - O(N^2).
Эмпирически это имеет смысл, потому что это в основном то, что я делал, и мое решение было мучительно медленным, но я думал, что удаление из списка, предполагая связанный список, было O(N) (или, в частности, O (N) для итерации до точки удаления, и O(1) для фактического удаления).
Моих знаний здесь явно не хватает, и я был бы очень признателен, если бы кто-нибудь мог помочь мне немного лучше понять, как это О (N ^ 2). Я могу как-то увидеть, как будет, если вы удаляете, а затем после каждого удаления пытаетесь снова найти в начале списка следующего эльфа, потому что в этом случае у вас есть стоимость N для каждого удаления. и снова N, чтобы найти следующего эльфа, итого N ^ 2. Хотя я делал счетчик того, где я был в списке, удаляя эльфа, а затем перебирал счетчик до следующей позиции. В этом случае я бы ожидал понести стоимость N для удаления, но не для индексации (возможно, в этом я и ошибаюсь, стоимость индексации).