Ожидаемое потребление места в списках пропусков
Какое ожидаемое пространство используется списком пропуска после вставки n элементов?
Я ожидаю, что в худшем случае потребление пространства может возрасти до бесконечности.
Википедия говорит "Космос O(n)".
Как это может быть доказано так или иначе?
3 ответа
Согласно этому тезису, который я считаю более надежным, чем википедия, википедия ошибочна. Список вероятностных пропусков Theta(nlogn) наихудший случай космической сложности.
Несмотря на то, что в среднем PSL работает достаточно хорошо, в худшем случае его пространство Theta(n lg n) и сложность времени Theta(n) неприемлемо высоки
Худший случай не бесконечен, потому что вы можете ограничить себя f(n) количество списков, где f(n) = O(logn) и перестаньте подбрасывать монеты, когда достигнете этой высоты. Итак, если у вас есть f(n) полные ряды, вы получите O(nlogn) общее количество узлов, таким образом, сложность пространства в этом случае O(nlogn), и не O(n),
РЕДАКТИРОВАТЬ:
Если вы ищете ожидаемое потребление пространства, а не худшее, как изначально было указано в вопросе, то:
Обозначим "столбец" как нижний узел, а все узлы "вверх" от него.
E(#nodes) = Sigma(E(#nodes_for_column_i)) (i in [1,n])
Вышеупомянутое уравнение верно, потому что линейность ожидаемого значения.
E(#nodes_for_column_i) = 1 + 1/2 + ... + 1/n < 2 (для каждого я). Это связано с тем, что с вероятностью 1 он имеет 1 узел, при p=1/2 у каждого из них есть дополнительный узел. при p'=1/2 у каждого из них есть дополнительный узел (всего p*p'=1/4),.... Таким образом, мы можем вывести:
E(#nodes) = n*E(#nodes_for_each_column) = n*(1+1/2+...+1/n) < 2n = O(n)
Давайте иметь детерминированный скиплист с N узлами. Помимо значений данных, список содержит:
N указателей на уровне 1, N/2 указателей на уровне 2, N/4 указателей на уровне 3 и так далее...
N + N / 2 + N / 4 + N / 8 +.. N / 2 ^ k - сумма геометрической прогрессии, и ее предел равен 2N, поэтому максимальное потребление памяти составляет N*SizeOf(Данные) + 2*N*SizeOf(Указатель) = O(N).
Я не принял во внимание межуровневые ссылки, но их количество примерно равно количеству указателей.
Ожидаемая космическая сложность
Пропустить список имеет logn слои. Каждый элемент в списке пропуска отображается в одном или нескольких слоях. Чтобы измерить ожидаемую сложность пространства списка пропусков, мы можем оценить ожидаемое количество слоев, в которых появляется произвольный элемент x.
Мы знаем, что x имеет 100% -ную вероятность появления только в нижнем слое, 50% -ную вероятность появления как в нижнем, так и во 2-м нижних слоях, 25% -ную вероятность появления в нижних 3-х слоях, 12,5% -ную вероятность появления в нижних 4 слоя и так далее.
Математически мы можем представить ожидаемое количество слоев, в которых появляется x, следующим образом...
Sum(i / 2^(i-1)) from i=1 to logn
... где i количество слоев, в которых может появиться x
Интуитивно понятно, что приведенное выше суммирование сходится к константе, поскольку знаменатель растет гораздо быстрее, чем числитель. Вы можете проверить это, подключив уравнение к Wolfram Alpha (суммирование сходится к 4 для очень больших значений n). Это подразумевает, что...
[Sum(i / 2^(i-1)) from i=1 to logn] = O(1)
Итак, мы продемонстрировали, что хранение произвольного элемента внутри произвольного списка пропусков требует в среднем постоянного пространства. Чтобы получить пространство сложность для хранения n элементы в списке пропуска, мы просто умножаем на n,
n*O(1) = O(n)
Таким образом, списки пропусков имеют линейную ожидаемую сложность пространства.
Наихудшая космическая сложность
Это на самом деле намного проще. Мы знаем, что есть logn слои и n элементы. В худшем случае каждый элемент находится в каждом слое. Следовательно, O(nlogn),