Анализ сложности очередей

Question

У меня есть две очереди, одна реализована с использованием массива для хранения, а другая реализована с использованием связанного списка.

Я считаю, что сложность операций enqueue и dequeue выглядит следующим образом -

LinkedListQueue Enqueue - O (1)

LinkedListQueue Dequeue- O (1)

ArrayQueueEnqueue - O (1)

ArrayQueue Dequeue - O (n)

Итак, я протестировал обе очереди, добавив и удалив из них строки. Вот результаты, которые я получил, время в миллисекундах -

Сложен ли мой анализ сложности по Оу с этими результатами? Сложность LLQueue Enqueue, которую я имею, заключается в O (1), но, как вы можете видеть, он варьируется от 2 мс для 1000 строк до 79 мс для 100000 строк. Это ожидается?

И у меня есть ArrayQueue Dequeue, помеченный как O (n), эти результаты выглядят как O (n)? Существует огромный скачок между 20000 и 50000 строками, но он только удваивается во времени при удалении из очереди 100000 строк вместо 50000. Это кажется немного странным ...

Answer 1

Во-первых, я удивлен тем, что ваша операция Dequeue на ArrayQueue настолько дорогая. Вы перемещаете все содержимое очереди в каждой очереди? Существует гораздо лучший подход - поискать «круговую очередь» онлайн.

Теперь перейдем к измерениям. Сложная сложность рассказывает только часть истории. Когда вы начнете измерять время работы, вы увидите множество сложных эффектов, таких как:

кэши

Похоже, ваш тест помещает кучу элементов в очередь, а затем удаляет их из очереди. Если вся очередь помещается в кэш L1 вашего процессора, все операции с памятью будут быстрыми.

Если размер очереди превышает кэш L1, данные должны будут пролиться в кэш L2, что может привести к замедлению в 2-3 раза. Если размер очереди превышает кэш L2, данные должны будут попасть в основную память, и вы получите еще одно значительное снижение производительности - скажем, в 5 раз.

Сборка мусора

Из названий ваших типов я бы предположил, что вы используете язык со сборкой мусора, такой как Java или C #. Если это так, то это означает, что ваша программа может сделать паузу в любое время (не совсем «в любое время», но сейчас это не важно) и потратить некоторое время на очистку памяти.

Другие эффекты

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

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