Итак, я видел этот вопрос о вероятностном потреблении пространства в списке пропусков:
но я думаю, что спрашивающий не понял, хочет ли он ожидаемого подхода или подхода наихудшего случая.
Поэтому я хотел бы снова поднять этот вопрос в полемику и объясню, почему я в замешательстве.
Для ясности: я ищу пространственную сложность вероятностного списка пропусков в наихудшем случае. Вот что я имел в виду:
С одной стороны, мы предполагаем, что максимальное число уровней равно log(n), легко сделать вывод, что в худшем случае у нас может быть n узлов на каждом уровне, что даст нам O(nlogn). С другой стороны, я предполагаю, что уровней может быть больше, чем log(n) (например, списки), и мы устанавливаем эту границу равной n — тогда мы получаем nn => O(n^2)
НО! Я не понимаю, почему мы имеем право ограничивать уровни, если новый уровень зависит от подбрасывания монеты, давайте считать, что в худшем случае мы получим бесконечное количество раз орел (а значит, новый уровень) и тогда мы различаем, что это даже не ограничено?! Я в замешательстве.
