难以理解数字表示与搜索 (0, N - 1) 的时间复杂度之间的关系？
Difficulty understanding the relation between the representation of a number and the time complexity of searching for (0, N - 1)?
不明白的直接资源请参考here
让我们取数字 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
==> log(10^d) > log(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 的 space 中搜索数字所需的最少操作数是 log(N)。
不明白的地方
This implies that, when asked to search for a number on the integer
line, ranging from 0 to N - 1, we need at least log(N) tries to find
it. Why? Any search algorithm will need to choose one digit after
another in its search for the number.
具体
Why? Any search algorithm will need to choose one digit after another
in its search for the number.
谁能给我看一下这方面的插图？
如果数组中有 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 范围内的值有何关系。
首先，他说的是任何可能存在的搜索算法的最短时间。如果你只有一个没有更多信息的未排序的数字列表，找到它需要的不仅仅是 log(N) 操作，但在这种情况下，我们可以使用诸如对列表进行预排序或创建索引之类的操作.完成后，您可以更快地进行搜索。
但是算法的搜索速度仍然有限。如果数字是n位长，则需要从输入中读取n位，即n次操作。所以如果你有一个数字 N，它有 floor(log(N)) + 1 个数字，所以你至少需要 floor(log(N)) + 1 个操作。在复杂性分析中，这是 O(log(N)) 阶数的一部分。您可能会争辩说算法可以一次读取整个数字，但对于非常大的数字而言并非如此。例如，一台 64 位计算机必须一次读取那些 2^64 位基数。
在链接的文本中，他将自己限制为以 10 为底，但这只是为了简化他的解释。如果您使用基数 10、基数 2 或基数 2^64，这同样有效。毕竟，base_A_log(x) = base_B_log(x) * log(A)/log(B)，因此所有对数函数仅相差一个常数因子。并且 O(C*log(N)) 与 O(log(N)).
的顺序相同
作为对您问题的回答：
"Why? Any search algorithm will need to choose one digit after another in its search for the number"
O(log(n)) 的搜索算法依赖于排序的数据，因此如果它检查一个元素并且该元素大于请求的元素，它可以丢弃之后的所有内容，因为所有这些都必须也会更大。
在计算机科学中，除非另有说明，否则日志通常被认为是以 2 为底的日志，我将其称为 lg(n) 以使其独一无二。
对于您的特定示例，假设您正在搜索“2”
O(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 步内得到答案。
不明白的直接资源请参考here
让我们取数字 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
==> log(10^d) > log(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 的 space 中搜索数字所需的最少操作数是 log(N)。
不明白的地方
This implies that, when asked to search for a number on the integer line, ranging from 0 to N - 1, we need at least log(N) tries to find it. Why? Any search algorithm will need to choose one digit after another in its search for the number.
具体
Why? Any search algorithm will need to choose one digit after another in its search for the number.
谁能给我看一下这方面的插图？
如果数组中有 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 范围内的值有何关系。
首先，他说的是任何可能存在的搜索算法的最短时间。如果你只有一个没有更多信息的未排序的数字列表，找到它需要的不仅仅是 log(N) 操作，但在这种情况下，我们可以使用诸如对列表进行预排序或创建索引之类的操作.完成后，您可以更快地进行搜索。
但是算法的搜索速度仍然有限。如果数字是n位长，则需要从输入中读取n位，即n次操作。所以如果你有一个数字 N，它有 floor(log(N)) + 1 个数字，所以你至少需要 floor(log(N)) + 1 个操作。在复杂性分析中，这是 O(log(N)) 阶数的一部分。您可能会争辩说算法可以一次读取整个数字，但对于非常大的数字而言并非如此。例如，一台 64 位计算机必须一次读取那些 2^64 位基数。
在链接的文本中，他将自己限制为以 10 为底，但这只是为了简化他的解释。如果您使用基数 10、基数 2 或基数 2^64，这同样有效。毕竟，base_A_log(x) = base_B_log(x) * log(A)/log(B)，因此所有对数函数仅相差一个常数因子。并且 O(C*log(N)) 与 O(log(N)).
的顺序相同作为对您问题的回答： "Why? Any search algorithm will need to choose one digit after another in its search for the number"
O(log(n)) 的搜索算法依赖于排序的数据，因此如果它检查一个元素并且该元素大于请求的元素，它可以丢弃之后的所有内容，因为所有这些都必须也会更大。
在计算机科学中，除非另有说明，否则日志通常被认为是以 2 为底的日志，我将其称为 lg(n) 以使其独一无二。
对于您的特定示例，假设您正在搜索“2” O(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 步内得到答案。