time-complexity - 程序的总时间复杂度？

Question

假设你在一个数组中输入 'n' 个输入(为此你必须运行一个循环，为 'n' 个不同的位置迭代 'n' 次)，这将具有 O(n) 复杂度。

然后您尝试执行时间复杂度为 O(log n) 或小于 O(n) 的操作。
我的问题是，这些操作的复杂度小于 O(n) 真的很重要，因为您的整个程序的时间复杂度至少为 O(n)。

Answer 1

实际上，程序的时间复杂度可能由读取输入所需的时间决定。例如，如果程序从输入中读取一个数组，然后在该数组中进行一次二分查找，时间复杂度为 Θ(n)，因为读取输入。

程序的时间复杂度也可能由生成输出所需的时间决定。例如，具有 n 个顶点的树有 n-1 条边，因此树上的许多算法可以在 Θ(n) 时间内运行；但是如果我们想打印 adjacency matrix那么没有办法在 Θ(n2) 时间内做到这一点，因为输出是具有 n2 个元素的二维数组。

我认为有一个隐含的后续问题:那么算法如何在小于 Θ(n) 的时间内运行？请注意，上面讨论的是执行 IO 的程序。 .二分搜索算法需要 Θ(log n) 时间，因为读取输入不是由二分搜索算法本身完成的。算法只是程序的一部分；该数组由程序的不同部分从输入中读取，因此在算法运行之前它存在于内存中，并且算法通过 reference 访问它。 .这意味着算法在 Θ(1) 时间内接收大小为 n 的输入。