如何解决Heapify重复向后替换的递归问题？

Question

所以我正在尝试解决复发问题

所以我有：

T(n) <= T(2n/3) + O(1)

We can write:

<= T(2n/3) + O(1)

<= T(4n/9) + 2O(1) 

...

<= T((2/3)^i * n) + i*O(1)

So if we solve for i

(2/3)^i * n = 1
(2/3)^i = (1/n)
i = log_(2/3)(1/n)

Which ten yields:

T((2/3)^(log_(2/3)(1/n)) + log_(2/3)(1/n)*O(1)

I.e.

T(1) + log_(2/3)(1/n)

So the time complexity would be: O(log_(2/3)(1/n))


Which could be also written as: O(-log_(2/3)(n))

Well, now it's negative. Is it still in O(log n)?

这是正确的吗？如果是，我如何从

O(log n) 

导出

O(log_(2/3)(1/n))

？

如果没有，你会怎么做？

我尝试自己解决这个问题，并在问题中写下了我的过程，这样如果我错了，人们也可以纠正我或添加内容。

Answer 1

看来我做对了，这里的想法是： 显然这是一个对数规则。

log_(a/b) (1/c) = log_(b/a) (c)，仅当 (a/b) < 1.

这意味着：

log(2/3) (1/n) = log_(3/2) (n)。

log_(3/2) (n) 的时间复杂度为 O(log n)。