由于读取输入必须采用 Θ(n)，那么某些算法怎么可能更快呢？例如，二分搜索是 O(log n)，但要读取数组或列表或任何正在搜索的内容，必须采用 Θ(n)（好像您不能跳过读取某些输入）。算法是否总是在假设它们有输入的情况下进行测量的？我真的不明白这一点，因为时间复杂度的全部意义在于找到瓶颈。如果我的问题没有意义，请直说。
问问题
687 次
3 回答
3
算法测量了它们对输入值所做的事情。读取输入不是算法的一部分。请注意，算法本身和读取输入并使用该算法的程序是不同的。
例如，二进制搜索具有 O(logn) 复杂度，但从文件中读取数字并应用二进制搜索查找数字的程序具有 O(logn)+O(n) = O(n) 复杂度。
于 2013-10-06T00:43:48.960 回答
2
通常，算法的运行时间不包括为处理准备数据所需的时间。没有根本原因必须这样，尽管这很好，因为对于需要亚线性时间的算法（例如，二进制搜索的 O(log n) 运行时间），我们不想考虑首先准备和排序数组所需的工作。
这种方法确实有几个优点。想象一下，您想多次执行某个操作（例如二分查找）。如果二进制搜索的复杂性包括准备和排序数组所需的成本，那么我们无法通过将二进制搜索的运行时间乘以 k 来获得“执行 k 个二进制搜索”的运行时间。我们必须花费二进制搜索的运行时间，减去准备输入所需的工作，将其乘以 k，然后再加上与设置所有内容相关的一次性成本。
也就是说，运行时分析通常确实包括生成输出所需的时间量。例如，如果您有一个生成 n 个值列表的算法，则它必须至少花费 Ω(n) 时间，因为您实际上无法在不做 n 个工作单元的情况下写出 n 个值。在首先分析算法时，通常会考虑此成本。有时您可以使用这一事实来证明具有某些运行时的算法不存在；例如，不可能有一种算法可以在小于 Ω(n) 的时间内生成 2 的前 n 次幂，因为你不能那么快地写出那么多数字。
我们通常会跳过问题的设置时间这一事实可以追溯到图灵机，在图灵机甚至开始运行之前，输入就被假设写在磁带上。
希望这可以帮助！
于 2013-10-06T00:49:11.050 回答
1
你的问题很有道理。复杂性取决于您如何定义算法的成本。该定义试图捕捉算法为世界增加的价值。考虑到这一点，您可以选择将在二分搜索中加载（以及排序）列表所花费的时间作为算法成本的一部分。这是有道理的，特别是如果您估计了您将在您正在分析的整个计算会话中执行的搜索操作的数量。
于 2013-10-06T00:50:00.197 回答