为什么二分搜索的时间复杂度为 O(log n)，而实际时间复杂度是阶跃函数？
Why does a binary search have a time complexity of O(log n), when the actual time complexity is a step function?
这是人们通常遇到的对数时间复杂度的定义：
Logarithmic running time O(log n) essentially means that the running time grows in proportion to the logarithm of the input size.
但在某些情况下，时间的增长似乎并不严格与输入大小的对数成正比。例如，考虑二分查找。据说该算法的时间复杂度为O(log n) 。我生成了大小从 2 到 1000 不等的数组，对于每个数组，我计算了最坏情况下的迭代次数（即数组拆分）。这是结果
显然，实际时间复杂度不是log2(n)（只有当log2(x)是整数时，两个函数的输出相同x）。
所以我的问题是，为什么我们说二分查找算法具有O(log n)复杂度，而时间复杂度实际上是阶跃函数？（以 1 = N/2^x 开始并经过一些代数运算以 x = log2(N) 结束的推导没有解释原因）
你的观察是对的。但是，big-O 是渐近符号。通常，在讨论时间复杂度时，我们对给出确切操作次数的函数不感兴趣，但我们感兴趣的是时间如何随输入大小而增长——具体来说，对于 sufficiently large 输入尺码。
如果您花点时间了解 big-O 的 definition，您会发现一些有趣的属性。其中一个 属性 是 O(f(n)) = O(c * f(n) + d)，其中 c > 0 和 d 是常数（如果 f(n) 不是常数）。
让我们从您的示例中获取阶跃函数 s(x)。我们知道对于任何 x，log(x) - 1 <= s(x) <= log(x)。我们认识到 -1 是一个常数，所以它遵循 O(s(x)) = O(log(x)).
这是人们通常遇到的对数时间复杂度的定义：
Logarithmic running time
O(log n)essentially means that the running time grows in proportion to the logarithm of the input size.
但在某些情况下，时间的增长似乎并不严格与输入大小的对数成正比。例如，考虑二分查找。据说该算法的时间复杂度为O(log n) 。我生成了大小从 2 到 1000 不等的数组，对于每个数组，我计算了最坏情况下的迭代次数（即数组拆分）。这是结果
显然，实际时间复杂度不是log2(n)（只有当log2(x)是整数时，两个函数的输出相同x）。
所以我的问题是，为什么我们说二分查找算法具有O(log n)复杂度，而时间复杂度实际上是阶跃函数？（以 1 = N/2^x 开始并经过一些代数运算以 x = log2(N) 结束的推导没有解释原因）
你的观察是对的。但是，big-O 是渐近符号。通常，在讨论时间复杂度时，我们对给出确切操作次数的函数不感兴趣，但我们感兴趣的是时间如何随输入大小而增长——具体来说，对于 sufficiently large 输入尺码。
如果您花点时间了解 big-O 的 definition，您会发现一些有趣的属性。其中一个 属性 是 O(f(n)) = O(c * f(n) + d)，其中 c > 0 和 d 是常数（如果 f(n) 不是常数）。
让我们从您的示例中获取阶跃函数 s(x)。我们知道对于任何 x，log(x) - 1 <= s(x) <= log(x)。我们认识到 -1 是一个常数，所以它遵循 O(s(x)) = O(log(x)).