由于读取输入必须取Θ（n），那么某些算法怎么可能更快？例如，二进制搜索为O（log n），但要读取数组或列表或正在搜索的任何内容，则必须取Θ（n）（这似乎不是您可以跳过读取某些输入）。是否总是在假设算法已经输入的情况下进行测量？我并没有真正意识到这一点，因为整个时间的复杂性在于找到瓶颈。如果我的问题没有道理，请这样说。
通常，算法的运行时不包括准备要处理的数据所需的时间。没有必要采用这种方式的根本原因，尽管这样做很不错，因为对于花费亚线性时间的算法（例如，二进制搜索的O（log n）运行时），我们不想考虑首先准备阵列并对其进行排序所需的工作。
这种方法确实具有几个优点。想象一下，您想多次执行某些操作（例如二进制搜索）。如果二进制搜索的复杂性包括准备和排序数组所需的成本，那么我们将二进制搜索的运行时间乘以k，就无法获得“执行k个二进制搜索”的运行时间。我们必须使用二进制搜索的运行时间，减去准备输入所需的工作，将其乘以k，然后加回与设置所有内容相关的一次性成本。
就是说，运行时分析通常确实包括生成输出所需的时间量。例如，如果您有一种算法可以生成n个值的列表，则它至少需要Ω（n）的时间，因为如果不进行n个工作单元就无法实际写出n个值。通常，首先要在分析算法时考虑此成本。您有时可以使用此事实来表明具有某些运行时的算法将不存在。例如，不可能有一个算法在时间上生成比Ω（n）小的前n个2的幂，因为您不能很快写出那么多的数字。
我们通常会跳过问题的建立时间这一事实的根源可以追溯到Turing机器，在Turing机器上，假设输入是在Turing机器甚至开始运行之前就被记录在磁带上的。
希望这可以帮助！
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句