Чем он отличается от асимптотического анализа? Когда вы его используете и почему? Я прочитал несколько статей, которые, кажется, были написаны хорошо, например: http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf...

Такие структуры необходимы для приложений реального времени — например, пользовательских интерфейсов. (Пользователей не волнует, занимает ли нажатие кнопки 0,1 с или 0,2 с, но их волнует, если 100-й щелчок приводит к выдающимся ленивым вычислениям и...

Когда я изучал курс Data Structures в университете, я усвоил следующие аксиомы: Вставка нового числа в кучу в худшем случае занимает O (logn) (в зависимости от того, насколько высоко в дереве он достигает при вставке в виде листа) Создание...

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

Предположим, вы реализуете кучу, используя массив, и каждый раз, когда массив заполняется, вы копируете его в массив, удвоенный по размеру. Какова амортизированная временная сложность (в худшем случае) вставки элементов в кучу? Я думаю, что у нас...

Структура данных поддерживает операцию foo, такую, что последовательность из n операций foo занимает Θ(n log n) время для выполнения в худшем случае. а) Каково амортизированное время операции foo? б) Насколько большим может быть фактическое...

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