搜索算法复杂度：您可以取一个数的 3/4 直到它小于或等于 1 的次数
Search Algo Complexity: Number of times you can take 3/4th of a number until it is less than or equal to 1
我正在研究二分搜索的一种变体，它可以在每次迭代时将搜索 space 缩小到原始大小的 3/4，我想知道您将如何计算它的运行时间。
我的直觉告诉我它是 N 的对数底数 (4/3)（其中 N = 您正在搜索的数组的大小），但我正在努力证明这一点。
是的，你是对的。
证明如下：
让我们从相反的方向来看。我们得到一个值 0 < n ≤ 1。在最后一次迭代之前，n 必须是这样的：
1 < n ≤ 4/3,
在 one-but-last 迭代之前：
4/3 < n ≤ (4/3)²
等等...所以回溯 k 次迭代我们得到：
(4/3)k−1 < n ≤ (4/3 )k
如果我们对这个不等式中的所有部分取以 (4/3) 为底的对数：
k − 1 < log4/3n ≤ k
因此，如果将该对数 向上舍入 ，您将得到 k，它表示迭代次数。
我正在研究二分搜索的一种变体，它可以在每次迭代时将搜索 space 缩小到原始大小的 3/4，我想知道您将如何计算它的运行时间。
我的直觉告诉我它是 N 的对数底数 (4/3)（其中 N = 您正在搜索的数组的大小），但我正在努力证明这一点。
是的，你是对的。
证明如下：
让我们从相反的方向来看。我们得到一个值 0 < n ≤ 1。在最后一次迭代之前，n 必须是这样的：
1 < n ≤ 4/3,
在 one-but-last 迭代之前：
4/3 < n ≤ (4/3)²
等等...所以回溯 k 次迭代我们得到：
(4/3)k−1 < n ≤ (4/3 )k
如果我们对这个不等式中的所有部分取以 (4/3) 为底的对数：
k − 1 < log4/3n ≤ k
因此，如果将该对数 向上舍入 ，您将得到 k，它表示迭代次数。