所以我看到了这个关于概率跳过列表空间消耗的问题:(答案)
但我认为提问者不清楚他想要一种预期的方法还是最坏的方法。
所以我想再次将这个问题提出来辩论,我会解释我为什么感到困惑。
需要明确的是 - 我正在寻找最坏情况下概率跳过列表的空间复杂度。这就是我的想法:
一方面,我们假设最大级别数是 log(n),很容易推断,在最坏的情况下,每个级别可能有 n 个节点,这会给我们 O(n logn)。另一方面,我假设可能有超过 log(n) 个级别(例如列表),我们将其设置为 n - 然后我们得到 n n => O(n^2)
但!我不明白为什么我们有权限制级别,如果新级别取决于抛硬币,我们假设在最坏的情况下我们将获得无限次正面(这意味着一个新级别)然后我们不同它甚至没有界限?!我很困惑。