Задача на поисследовать

[mitrik]

Добрый день! Коллеги подкинули задачу на "поисследовать"

Изначально дан массив, каждый элемент которого равен нулю. С массивом возможно проводить операции 2 типов:

1. сделать инкремент i-го элемента на 1,
2. получить индекс элемента с минимальным значением.

Предложить структуру данных, которая позволяет выполнять указанные операции над массивом и требует

1)минимум затрат по дополнительной памяти
2)минимум затрат по сложности

Из нее вытекают вопросы:

1) Если минимум по памяти, то, получается, что мы храним только сам массив и все. Тогда поиск минимума производится за $O(n)$, а инкремент за единицу. Либо можно сделать как-то оптимальнее?

2) Если минимум по сложности, то, логично, что можно положить болт на память и пользоваться ей в свое удовольствие. По умолчанию у нас массив отсортированный. При инкременте одного элемента нам надо его "пересортировать", посему - можно ли это сделать за O($\log(n)$)? Потому как за логарифм мы только найдем куда вставить увеличенный элемент, но надо же еще провести смещение блока отсортированного массива(поиск этого элемента можно не проводить, если в структуре хранить вместе со значением и номером элемента первоначального массива еще и его адрес в отсортированном массиве). Тогда, соответственно, поиск минимума - за единицу, а инкремент за логарифм(если это возможно). Вопрос - прав ли я и можно ли сделать быстрее?

Буду благодарен не за прямые ответы, а за любые наводящие вопросы, чтобы по итогу додумался сам. Спасибо

[rockclimber]

Если мы увеличиваем один элемент на единицу за раз, то для сортировки достаточно сравнить элемент с соседом и поменять их местами. Получится такой "медленный пузырек". Изредка будет получаться смещение больше чем на одну позицию, но мне лень считать, сколько получится в итоге. Точно меньше $O(n)$ при дополнительных затратах памяти на вторую копию массива.

[realeugene]

mitrik в сообщении #1325824 писал(а):

2)минимум затрат по сложности

Вас интересует средняя сложность или в худшем? Потому что в случае прибавления единицы к случайно и независимо выбираемому элементу в сортированном массиве, эти элементы, конечно, будут переставляться иногда друг с другом, но чем дальше - тем реже.

[mitrik]

realeugene в сообщении #1325836 писал(а):

Вас интересует средняя сложность или в худшем? Потому что в случае прибавления единицы к случайно и независимо выбираемому элементу в сортированном массиве, эти элементы, конечно, будут переставляться иногда друг с другом, но чем дальше - тем реже.

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

[rockclimber]

mitrik в сообщении #1325839 писал(а):

Все-таки искать минимум за линейную сложность при неограниченной памяти не очень хочется

Если вы сортируете при вставке, то поиск у вас будет за $O(1)$ - тупо первый элемент сортированного массива. Расходы будут на сортировку.

[mitrik]

rockclimber в сообщении #1325842 писал(а):

Если вы сортируете при вставке, то поиск у вас будет за $O(1)$ - тупо первый элемент сортированного массива. Расходы будут на сортировку.

Да, пардон, сам в своих словах запутался. Почему-то кажется, что именно эту часть можно минимизировать, только не придумал как. Смещение массива влево, в худшем случае будет иметь линейную сложность

[mustitz]

А просто хранить в виде кучи пары значение/индекс?

Двоичная куча
Биномиальная куча
Фибоначчиева куча

Фибоначчиева куча, похоже, самое то:

Цитата:

Кроме стандартных операций INSERT, MIN, DECREASE-KEY, фибоначчиева куча позволяет за время $O(1)$ выполнять операцию UNION слияния двух куч.

[mitrik]

mustitz в сообщении #1325848 писал(а):

А просто хранить в виде кучи пары значение/индекс?

А как в таком случае производить сам инкремент? А точнее поиск нужного индекса? Куча же будет построена относительно значений

[EUgeneUS]

1. Храним индекс минимального элемента. Больше ничего. (upd: соответственно, возвращаем минимальный элемент всегда за O(1))
2. Массив не сортируем.
3. Инкрементируем за O(1).
4. Если инкрементировали не минимальный элемент, то и прекрасно.
5. Если инкрементировали минимальный элемент, то ищем новый минимальный и запоминаем его индекс. Например, один проход пузырька за O(n)

Так как пункт 5 реализуется в одном случае из n, то в среднем он даст добавку к сложности O(1).

[mustitz]

mitrik в сообщении #1325851 писал(а):

mustitz в сообщении #1325848 писал(а):

А просто хранить в виде кучи пары значение/индекс?

А как в таком случае производить сам инкремент? А точнее поиск нужного индекса? Куча же будет построена относительно значений

Мы храним оригинальный индекс элемента $i$, он неизменен. И мы храним текущее значение $v$, которое можно инкрементировать. Соответственно, чтобы получить индекс наименьшего элемента мы просто берём верхушку кучи и возвращаем оттуда индекс. Инкремент узла $(i, v)$ это по сути изменение значения на $(i, v+1)$. Вопрос только в том, что это увеличение значения ключа (а не уменьшение), и Фиббоначиева куча скорее всего не будет работать :( Но по крайней мере направление движения ясно. Но даже простая замена изменения на две операции удалить/добавить в случае если если инкремет меняет расположение узлов (простая проверка) даст нам $O(\log N)$.

[realeugene]

mitrik в сообщении #1325839 писал(а):

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

Пузырёк в худшем даёт $O(N)$ конечно. Если только параллельно с сортированным списком не хранить список интервалов в этом списке с одинаковыми значениями элементов. Тогда вспылытие элемента при инкременте его значения можно выполнить за $O(1)$.

[mihaild]

EUgeneUS в сообщении #1325853 писал(а):

Так как пункт 5 реализуется в одном случае из n, то в среднем он даст добавку к сложности O(1).

Может и каждый раз реализовываться.

rockclimber в сообщении #1325832 писал(а):

Изредка будет получаться смещение больше чем на одну позицию, но мне лень считать, сколько получится в итоге. Точно меньше $O(n)$ при дополнительных затратах памяти на вторую копию массива.

Может почти всегда получаться больше, если всегда увеличивать самый левый элемент. Таким образом из всех нулей получим все единицы за $(n - 1) + (n - 2) + \ldots + 1$ сдвигов и $n$ инкрементов.

Но за $O(1)$ всё равно можно - нужно хранить сортированный связный список (значение, связный список элементов с этим значением) (ну и для каждого индекса - где в каком списке он лежит). При увеличении элемента переносим его в следующий список верхнего уровня (при необходимости создаем), ставшие пустыми списки убираем. Каждый инкремент и поиск минимума делается строго за константу.

[EUgeneUS]

mihaild в сообщении #1325867 писал(а):

Может и каждый раз реализовываться.

Может, поэтому O(1) только в среднем, а в худшем O(n), конечно.
И что-то мне подсказывает, что без создания новых структур данных ("индексов") лучше не сделать.

[realeugene]

Можно ещё выполнить эти операции за амортизированное время O(1) и всего с двумя дополнительными ячейками памяти. Например, мы кроме самого массива храним индекс последнего найденного минимального элемента и его значение. Инициализируя индексом последнего элемента в массиве и значением -1 (впрочем, два нуля тоже работают). При запросе минимума выдаём текущий последний индекс, если его значение совпадает со старым, или идём в конец массива и далее по кругу, ища первое совпадение, и при возврате в начало массива увеличивая искомое значение на 1.

PS Ну как, "поисследовали"?

PPS Да и одной дополнительной ячейкой памяти на список можно обойтись. Нужно проводить подобный поиск нового минимума всякий раз, когда инкрементируется значение старого минимума

[mitrik]

EUgeneUS в сообщении #1325853 писал(а):

1. Храним индекс минимального элемента. Больше ничего. (upd: соответственно, возвращаем минимальный элемент всегда за O(1))
2. Массив не сортируем.
3. Инкрементируем за O(1).
4. Если инкрементировали не минимальный элемент, то и прекрасно.
5. Если инкрементировали минимальный элемент, то ищем новый минимальный и запоминаем его индекс. Например, один проход пузырька за O(n)

Так как пункт 5 реализуется в одном случае из n, то в среднем он даст добавку к сложности O(1).

Этот вариант, на самом деле шикарно подходит под пункт с минимальными затратами по памяти, т.к. про время там ничего не сказано, а ,в общем случае, работает явно быстрее пузырька.

mustitz в сообщении #1325857 писал(а):

Мы храним оригинальный индекс элемента $i$, он неизменен. И мы храним текущее значение $v$, которое можно инкрементировать. Соответственно, чтобы получить индекс наименьшего элемента мы просто берём верхушку кучи и возвращаем оттуда индекс. Инкремент узла $(i, v)$ это по сути изменение значения на $(i, v+1)$. Вопрос только в том, что это увеличение значения ключа (а не уменьшение), и Фиббоначиева куча скорее всего не будет работать :( Но по крайней мере направление движения ясно. Но даже простая замена изменения на две операции удалить/добавить в случае если если инкремет меняет расположение узлов (простая проверка) даст нам $O(\log N)$.

Насчет кучи подумаю как это можно реализовать, идея точно жизнеспособная, хоть и геморройная немного)))

mihaild в сообщении #1325867 писал(а):

Но за $O(1)$ всё равно можно - нужно хранить сортированный связный список (значение, связный список элементов с этим значением) (ну и для каждого индекса - где в каком списке он лежит). При увеличении элемента переносим его в следующий список верхнего уровня (при необходимости создаем), ставшие пустыми списки убираем. Каждый инкремент и поиск минимума делается строго за константу.

Так удаление элемента по значению из списка вроде линейная операция или я что-то совсем попутал?