algorithm - 难以理解数字的表示与搜索 (0, N - 1) 的时间复杂度之间的关系？

Question

请参考这里我不明白的直接资源。

让我们取数字 X = 245436，我们可以将以下表示为 X = 2 * 10^5 + 4 * 10^4 + 5 * 10^3 + 4 * 10^2 + 3 * 10^1 + 6 * 10^ 0 使用十进制扩展。所以，我们需要代表这个数字的最少信息量是 6 位数字。这并非巧合，因为任何小于 10^d 的数字都可以用 d 位表示。

那么代表 X 需要多少位数字呢？这等于 X 中 10 的最大指数加 1。

==> 10^d > X

==> 日志（10^d）> 日志（X）

==> d* log(10) > log(X)

==> d > log(X) ...日志再次出现...

==> d = floor(log(x)) + 1

我可以通过他的插图和例子来理解，但让我感到困惑的是下一个例子。当他尝试关联搜索 0 -> N -1 范围内的数字时。

这是他的解释：

取 N = 10^d，我们使用最重要的观察结果：

唯一标识 0 到 N - 1 = log(N) 位范围内的值的最小信息量。

这意味着，当被要求在整数行上搜索一个从 0 到 N - 1 的数字时，我们至少需要 log(N) 次尝试找到它。为什么？任何搜索算法在搜索数字时都需要一个接一个地选择一个数字。

它需要选择的最小位数是 log(N)。因此，在大小为 N 的空间中搜索数字所需的最小操作数是 log(N)。

我不明白的

这意味着，当被要求在整数行上搜索一个从 0 到 N - 1 的数字时，我们至少需要 log(N) 次尝试找到它。为什么？任何搜索算法在搜索数字时都需要一个接一个地选择一个数字。

具体来说

为什么？任何搜索算法在搜索数字时都需要一个接一个地选择一个数字。

有人可以给我看一个例子吗？

如果我们在一个数组中有 10 个元素（n = 10）

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

我试图找到什么索引给了我 5 的值？这意味着我需要 log(10) 尝试找到它？首先以 10 为底的对数？那是 log 10 = 1。我不明白这有什么意义？如果我使用基数 2，我得到 = 3。

这意味着我至少要进行 3 次操作才能找到 x？为什么？有人可以说明吗？

我只是不明白十进制扩展与查找 0 - n 范围内的值有何关系。

标签： algorithmmathtime-complexitybig-ologarithm

Answer 1

作为对您问题的回答：“为什么？任何搜索算法都需要在搜索数字时选择一个接一个的数字”

O(log(n)) 的搜索算法依赖于被排序的数据，因此如果它检查一个元素并且该元素大于请求的元素，它可以丢弃之后的所有内容，因为所有这些也必须更大。

在计算机科学中，除非另有说明，否则日志通常被认为是基于 2 的日志，我将其称为 lg(n) 使其唯一。

对于您的特定示例，假设您正在搜索“2” AO(log(n)) 算法将类似于如下工作。0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

检查中间元素，4。4是否大于2？是的。因此，忽略 4 之后的所有内容并检查 0 和 4 之间的中间值。2 是中间值，我们分 2 步找到该数字。在最坏的情况下，它需要 floor(lg(n)) + 1 步，因为每次将未检查元素的数量除以 2 时，+ 1 来自边缘情况。此外， floor(lg(n)) + 1 指的是最坏的情况，而不是最好的情况。在最好的情况下，这个特定的算法可以在 1 步中得到答案。