Хорошо, давайте так: у вас есть очередь с приоритетом. Вам надо внутре хранить данные. При этом при извлечении нужно гарантировать, что высокий приоритет пойдет первым, а внутри одного приоритета - по времени добавления (Можно и иначе, но я хочу - такую очередь). Теперь понятно, что без ограничения общности мы можем считать, что у нас только одно данное каждого приоритета (грубо говоря, если мы считаем, что храним не отдельные сообщения, а в виде FIFO для каждого приоритета отдельно, то и - опаньки: FIFO эto O(1) на ввод-вывод). Таким образом вопрос - надо как-то организовать набор данных, чтобы их можно было извлекать в определенном порядке. Задачка знакомая. Ответ известен: если набор приоритетов конечен, - скажем, целые числа от 0 до 99, то создаем массив размером 100, куда пишем - по индексу. Результат - O(1). Однако, если нам надо поддерживать произвольные приоритеты - О(logM), где М - количество приоритетов в системе.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
no subject
Date: 2003-05-30 05:54 pm (UTC)Теперь понятно, что без ограничения общности мы можем считать, что у нас только одно данное каждого приоритета (грубо говоря, если мы считаем, что храним не отдельные сообщения, а в виде FIFO для каждого приоритета отдельно, то и - опаньки: FIFO эto O(1) на ввод-вывод).
Таким образом вопрос - надо как-то организовать набор данных, чтобы их можно было извлекать в определенном порядке. Задачка знакомая. Ответ известен: если набор приоритетов конечен, - скажем, целые числа от 0 до 99, то создаем массив размером 100, куда пишем - по индексу. Результат - O(1). Однако, если нам надо поддерживать произвольные приоритеты - О(logM), где М - количество приоритетов в системе.