假设你在数组中获取"n"个输入(为此你必须运行一个循环，为"n"个不同的位置迭代"n"次(，这将具有O(n(的复杂性。
然后，您尝试执行具有O(log n(或小于O(n(时间复杂度的操作。 我的问题是，这些操作的复杂性低于 O(n( 真的重要吗，因为你的整个程序至少会有 O(n( 的时间复杂度。
事实上，程序的时间复杂度可能由读取输入所需的时间决定。例如，如果一个程序从输入中读取一个数组，然后在该数组中进行一次二进制搜索，则时间复杂度仅为 Θ(n(，仅仅是因为读取输入。
程序的时间复杂度也可能由生成输出所需的时间决定。例如，具有 n 个顶点的树有 n-1 条边，因此树上的许多算法可以在 Θ(n( 时间内运行;但是如果我们想打印邻接矩阵，那么就没有办法在比 Θ(n 2( 更好的时间内做到这一点，因为输出是一个包含 n个2 个元素的 2D 数组。
我认为有一个隐含的后续问题：那么算法如何在不到 Θ(n( 的时间内运行？请注意，上面讨论的是执行IO的程序。二叉搜索算法需要 Θ(log n( 时间，因为读取输入不是由二叉搜索算法本身完成的。算法只是程序的一部分;数组由程序的不同部分从输入中读取，因此在运行算法之前它存在于内存中，并且算法通过引用访问它。这意味着算法以 Θ(1( 时间接收其大小为 n 的输入。
不，这在 big-O 术语中并不重要，因为在您的示例中，输入循环O(n)在进一步的O(log n)操作中占主导地位。参见无限渐近：
大 O 表示法在分析算法的效率时很有用。例如，完成大小为 n 的问题所需的时间(或步骤数(可能会发现为 T(n( = 4n2 − 2n + 2。随着 n 变大，n2 项将占主导地位，因此所有其他项都可以忽略不计