时间复杂度问题：O(n)与O(Log n)差异及函数相加复杂度

1. O(n)与O(log n)的时间复杂度区别及O(log n)时间、O(n)空间函数说明 #

两者核心区别 #

• 增长速率：O(n)是线性增长，算法执行时间随输入规模n的增大呈线性上升；O(log n)是对数增长，增长速率远慢于线性。当n达到较大数值时（比如n=10000，log₂n≈14），O(log n)的执行时间会比O(n)小几个数量级。
• 典型应用场景：
  • O(n)常见于线性遍历操作，比如逐个遍历数组元素、计算数组总和等。
  • O(log n)多见于分治类算法，比如二分查找、平衡二叉树的查询/插入操作，这类算法每次都会将问题规模缩减为原来的一半。

O(log n)时间、O(n)空间的函数说明 #

这类函数的特点是时间效率极高，但空间消耗与输入规模线性绑定，属于典型的「空间换时间」策略。举个实际例子：预先开辟一个大小为n的数组存储输入数据（空间O(n)），然后基于这个数组执行二分查找操作（时间O(log n)）；或是某些分治算法中，为了避免重复计算，用一个大小为n的缓存数组存储中间结果，从而将时间复杂度优化到O(log n)。需要注意的是，当n过大时，线性空间的占用可能会成为内存瓶颈。

2. 多组时间复杂度相加后的结果 #

时间复杂度相加时，遵循保留最高阶增长项，忽略低阶项与常数系数的大O表示规则，结果如下：

• log n与log n：同阶项相加，常数系数不影响大O表示，最终时间复杂度为O(log n)。
• log n与n：n的增长速率远快于log n，低阶项可忽略，最终时间复杂度为O(n)。
• n与n：相加后为2n，常数系数忽略，最终时间复杂度为O(n)。

内容的提问来源于stack exchange，提问作者Gary