python - O(log n) 的时间复杂度嵌套在另一个 O(log n) 循环中

Question

我对以下算法的时间复杂度有点困惑。我知道插入堆是 O(log n)，基数为 2，但是嵌套在内部的 while 循环似乎是 O(log n)，基数为 3。时间复杂度是否为 O(log n，基数为 3) * O(log n 以 2 为底)?

i = 1
while i < len(L):
    insert L[i] into heap
    i = i*3

Answer 1

由于 i 呈指数增长，您将向 heap 中插入 floor(log3(L)) 元素。

假设插入是O(log(n))，其中n是堆中已有的元素数(不是数组 L)，对初始为空的堆执行 m 插入操作的复杂度为 O(log 1 + log 2 + log 3 + ... log (m - 1)) = O(log([m - 1]!) = O(log(m!))。

根据斯特林近似，ln(n!) = n ln n - n + O(ln n)。

代入插入次数，并忽略被掩盖的 O(n) 项，我们有:

T(L) = O(log([floor(log3(L))]!))
     = O([floor(log3(L))][log(floor(log3(L)))])  // apply Stirling
     = O([log3(L)][log(log3(L))])  // a number rounded down only differs
                                      from its value by less than 1
     = O(log L * log log L)        // base of log only contributes to a constant