假设您在数组中获取“n”个输入(为此，您必须运行一个循环，为“n”个不同位置迭代“n”次)，这将具有 O(n) 复杂度。
然后你尝试执行时间复杂度为 O(log n) 或小于 O(n) 的操作。 我的问题是，这些操作的复杂度小于 O(n) 真的很重要吗，因为整个程序的时间复杂度至少为 O(n) 。
最佳答案
事实上，程序的时间复杂度可能取决于读取输入所需的时间。例如，如果程序从输入中读取一个数组，然后在该数组中进行一次二分查找，则时间复杂度为 θ(n)，因为读取输入。
程序的时间复杂度也可能由生成输出所需的时间决定。例如，一棵有 n 个顶点的树有 n-1 条边，因此树上的许多算法可以在 θ(n) 时间内运行；但如果我们想打印adjacency matrix那么就没有办法在比 θ(n2) 更好的时间内完成此操作，因为输出是一个包含 n2 元素的二维数组。
我认为有一个隐含的后续问题:那么算法如何在少于 θ(n) 的时间内运行？请注意，上面讨论的是执行 IO 操作的程序。 。二分搜索算法需要 θ(log n) 时间，因为读取输入不是由二分搜索算法本身完成的。算法只是程序的一部分；该数组是由程序的不同部分从输入中读取的，因此在运行算法之前它就存在于内存中，并且算法可以通过 reference 访问它。 。这意味着算法在 θ(1) 时间内接收大小为 n 的输入。
关于time-complexity - 程序的总体时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/60063034/