Действительно ли амортизация когда-либо действительно желательна?

Question

Например, предположим, у меня есть алгоритм O (n) и алгоритм амортизации O (n). Справедливо ли говорить, что, если говорить строго о, неамортизированный алгоритм всегда будет таким же быстрым или быстрым, чем амортизированный? Или есть ли причина предпочитать амортизированную версию (игнорируя такие вещи, как простота кода или простота реализации)?

Answer 1

1. Обозначение Big O говорит только о том, как масштабируется ваш код, а не о том, как быстро он будет работать для конечного N.
2. Разница между амортизированной и не амортизированной важна, если вы заботитесь о производительности в худшем случае или о задержке (например, в реальном времени или в интерактивных системах). Если вы заботитесь только о средней пропускной способности, они практически одинаковы для всех практических целей. Амортизированный анализ достаточно хорош даже в некоторых критических ситуациях, таких как научные вычисления и крупномасштабный анализ данных.

Answer 2

Или когда-нибудь есть причина отдавать предпочтение амортизированной версии

Меньшие константы.

Answer 3

Основное различие между алгоритмом O (n) и алгоритмом амортизации O (n) состоит в том, что вы ничего не знаете о поведении наихудшего случая алгоритма амортизации O (n). На практике это не имеет большого значения: если ваш алгоритм запускается много раз, вы можете рассчитывать на закон средних значений, чтобы уравновесить несколько плохих случаев, и если ваш алгоритм не запускается очень много раз, тогда маловероятно, что вы когда-либо столкнетесь с наихудшим случаем.

Единственные случаи, когда слово «амортизировано» должно иметь значение, - это случаи, когда вы по какой-то причине не можете принять иногда плохую работу. Например, в приложениях с графическим интерфейсом вы бы с радостью отказались от некоторой средней производительности в обмен на гарантию того, что вы никогда не застрянете и не перестанете отвечать, пока пользователь сидит и скучает. В таких приложениях вы хотите убедиться, что даже наихудшее поведение подходит для любого кода, который может привести к тому, что графический интерфейс перестанет отвечать.

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

Answer 4

Классическим примером необходимости использования амортизированного алгоритма будет std :: vector, для которого вставка амортизируется O (1).

Некоторые причины использования амортизированных алгоритмов:

• Гораздо эффективнее средний случай.
• Упрощенная реализация.
• Не существует алгоритма гарантии худшего случая.

Answer 5

Обозначение Big O говорит вам о том, как ваш алгоритм меняется с ростом ввода. Это не ярлык для профилирования вашего кода.

Возможно, лучшим алгоритмом является O (n ^ 2) для всех n в вашей программе, потому что в O (n) есть константа, которая больше.

Таким образом, ваш выбор алгоритмов действительно зависит от того, какой алгоритм быстрее для вашего размера ввода. Я думаю, что ответ на ваш вопрос заключается в профилировании обоих алгоритмов в вашей программе, а затем решить, что быстрее.

Answer 6

Строго говоря, big-O не является достаточно точной мерой, чтобы можно было сказать, что алгоритм с O (n) быстрее, чем алгоритм с амортизированным O (n).Думаю об этом.Если вы снизите уровень достоверности в своем анализе сложности, постоянные коэффициенты могут значительно отличаться и сделать амортизированную версию более быстрой.

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

Вот почему амортизация отличается от наихудшего случая.Big-O отражает наихудший случай, в то время как амортизация позволяет вам сказать, что «один на каждый x будет попадать, а x достаточно большой, чтобы это не имело значения».Кроме того, если вы рассматриваете примеры, такие как вставка в хеш-таблицу, x увеличивается в соответствии с некоторой константой.Таким образом, если у вас есть хеш-таблица, которая начинается со 100 сегментов и удваивается каждый раз, тогда эти повторы асимптотически будут становиться все дальше и дальше друг от друга.Кроме того, абсолютная сложность в наихудшем случае для алгоритма с амортизированной сложностью зависит от предыдущих вызовов, тогда как в показателях, подобных среднему, вызовы считаются независимыми.