Описание тега amortized-analysis

Описание тега Вопросы с тегом
Амортизированный анализ - это анализ общего времени выполнения набора операций, а не отдельного времени выполнения какой-либо одной операции.
0 ответов

Реализация Deque с использованием 3 стеков (амортизированное время O(1))

У меня есть этот вопрос для howmework: Реализуйте Deque, используя 3 стека. У Deque есть такие операции: InsertHead, InsertTail, DeleteHead,DeleteTail. Докажите, что амортизированное время для каждой операции равно O(1). То, что я пытался, это посмо…
10 май '14 в 19:43
1 ответ

Редактирование: как спроектировать и реализовать эксперимент для сравнения производительности двух реализаций очереди в python

Я ищу указатели на то, как разработать эксперимент, чтобы сравнить поведение queue реализации один сделано с python list и другие python queue abstract data type используя тест Вот код, который я мог бы вынести на основе того, как я понял amortized …
24 авг '16 в 08:48
0 ответов

Анализ амортизированного времени в мин куче

У меня есть минимальная куча, которая содержит k чисел со счетчиком того, сколько раз мы получили это число от пользователя (например, мы могли бы иметь число 5 со счетчиком 0, чтобы не отображаться в пользовательском вводе). Функция вставки выполня…
21 июл '18 в 13:19
0 ответов

N-разрядный счетчик амортизированного анализа

Предположим, у нас есть двоичный счетчик, который поддерживает две операции: увеличение и сброс всех битов до нуля. Если модификация или проверка одного бита занимает время тета (1), как счетчик может быть реализован как массив битов, чтобы любая по…
05 окт '12 в 01:39
0 ответов

Как рассчитать дату погашения кредита по кредиту

Я хочу рассчитать амортизацию кредита, но не знаю, как рассчитать дату выплаты. я имею Loan amount,Interest rate,Monthly paymnet,Loan Start date, Из этих четырех значений я хочу узнать дату погашения кредита в iOS. я считаю Interest,Monthly Amount к…
09 окт '15 в 02:01
1 ответ

Каково амортизированное время нахождения элемента-преемника в бинарном дереве поиска с использованием алгоритма inorder?

Как я могу амортизировать анализ и доказать, что функция-преемник (та, которая находит следующий элемент в алгоритме переупорядочения) принимает в среднем O(1)? Предполагая, что функция-преемник работает с последним найденным элементом. Это даже O(1…
13 дек '17 в 14:19
2 ответа

Алгоритм объединения / поиска без объединения по рангу для структуры данных о лесах с непересекающимся множеством

Вот разбивка алгоритма объединения / поиска для непересекающихся наборов лесов в Википедии: Barebone непересекающиеся набор леса... (O(n)) ... с объединением по рангу... (теперь улучшено до O(log(n)) ... со сжатием пути (теперь улучшено до O(a(n))эф…
24 фев '10 в 02:53
1 ответ

Анализ сложности времени для цикла:

Почему сложность времени O(n) вместо O(nlogn)? Разве вам не нужно умножать сложность внешнего цикла на сложность внутреннего цикла? int fun(int n){ int count = 0; for (int i = n; i > 0; i /= 2) for (int j = 0; j < i; j++) count += 1; return co…
30 май '15 в 15:13
2 ответа

Амортизированное время динамического массива

В качестве простого примера, в конкретной реализации динамического массива мы удваиваем размер массива каждый раз, когда он заполняется. Из-за этого может потребоваться перераспределение массива, а в худшем случае для вставки может потребоваться O(n…
31 янв '11 в 17:28
3 ответа

Почему сложность по времени метода Python list.append() O(1)?

Как видно из документации по TimeComplexity, Python list Тип реализован с использованием массива. Поэтому, если используется массив, и мы делаем несколько добавлений, в конечном итоге вам придется перераспределить пространство и скопировать всю инфо…
09 окт '15 в 18:24
1 ответ

Амортизированный анализ на счетчике мощности 3

Я читал учебники по алгоритмам Кормена, Лизерсона, Ривеста и Штейна чаще, чем нет. Одна из интересных глав там - Амортизированный анализ. Двоичный счетчик - сложный пример, когда дело доходит до выбора Потенциальных функций. Мне было интересно, что …
11 сен '18 в 00:53
2 ответа

Амортизированный анализ алгоритмов

Я сейчас читаю амортизированный анализ. Я не в состоянии полностью понять, чем он отличается от обычного анализа, который мы выполняем для вычисления среднего или наихудшего поведения алгоритмов. Может кто-нибудь объяснить это на примере сортировки …
22 дек '12 в 11:21
1 ответ

Как я могу обеспечить амортизацию O(n) от Data.Vector?

У меня есть приложение, в котором эффективно использовать Векторы для одной части кода. Однако во время вычислений мне нужно отслеживать некоторые элементы. Я слышал, что вы можете получить O(n) амортизированную конкатенацию от Data.Vectors (обычным…
27 окт '11 в 09:19
0 ответов

Кучи Фибоначчи без индексации массива?

Друзья, мой профессор покрывал кучи Фибоначчи и давал домашнюю работу. Требование обычно после извлечения, нам нужно сжать корневой список, связав корни той же степени. Мы используем индексирование массива, чтобы найти другой элемент такой же степен…
14 ноя '11 в 00:08
1 ответ

Поиск и удаление за время (log n) с использованием массивов

Предположим, нам изначально дан набор из n чисел. Нам нужно построить структуру данных, которая поддерживает запросы Search(), Predecessor() и Deletion(). Поиск и Предшественник должны занять наихудший случай O(обработка журнала n) время. Удаление д…
11 ноя '15 в 11:32
1 ответ

Обновление максимальной суммы субинтеграла в массиве за сублинейное время при применении смежного преобразования

Я задавал этот вопрос для общих транспозиций, и это казалось слишком сложным, я получил только один ответ, который, казалось, не давал гарантированного асимптотического ускорения. Итак, предположим, что мы применяем последовательность смежных трансп…
16 янв '14 в 18:42
0 ответов

Анализ наилучшего случая, среднего случая, наихудшего случая и амортизированного случая

Я ищу понимание того, как все работает, а не просто ответ. Я даю то, что, как я думаю, ответ, но я не совсем уверен, и текст не имеет особого отношения к такого рода анализу. Я прекрасно понимаю, что это НЕ то, как вы должны реализовывать стек, но э…
30 янв '13 в 13:38
1 ответ

Амортизированный анализ

Я столкнулся с этой проблемой при изучении, которая просит рассмотреть структуру данных, где выполняется последовательность из n операций. Если k-я операция имеет стоимость k, если это идеальный квадрат, а стоимость 1 в противном случае, какова обща…
12 дек '15 в 18:17
1 ответ

Амортизированный анализ и конкурс Questiosn, есть какие-нибудь проблемы?

Я столкнулся с вопросом местного конкурса следующим образом. Если на пустом MIN-Heap мы делаем n произвольный insert а также delete операции, (с заданным местоположением удаления в мин-куче). что amortized analysis за insert а также delete? I) встав…
09 апр '15 в 11:11
1 ответ

Haskell векторный C++ push_back аналог

Я обнаружил, что Хаскелл Data.Vector.* скучаю по С ++ std::vector::push_backфункциональность. Есть grow/unsafeGrow, но они, кажется, имеют сложность O(n). Есть ли способ вырастить векторы за O(1) амортизированного времени для элемента?
23 июл '15 в 21:24