O(log n)与O(log n +1)的时间复杂度是否存在差异？

一、快速搞懂时间/空间复杂度 #

• 时间复杂度：核心看数据量n变大时，算法执行次数的增长趋势，不用抠具体次数。比如：
  • 逐行遍历数组，n翻倍时执行次数也翻倍，就是O(n)；
  • 二分查找这类每次把数据量砍半的操作，n翻倍时执行次数只加1，就是O(log n)；
  • 嵌套两层遍历，n翻倍时执行次数变成4倍，就是O(n²)。
• 空间复杂度：看算法运行时额外占用的内存随n的增长趋势。比如：
  • 只用了几个固定变量，不管n多大内存都不变，就是O(1)；
  • 开了一个和输入数据量一样大的数组，内存随n同步增长，就是O(n)。

可以用生活化类比：找书架上的书，逐本翻是O(n)，按索引跳着找（二分）是O(log n)；装水果，用固定大小的篮子是O(1)，用能装n个的纸箱是O(n)。

二、O(log n +1)与O(log n)是否等价？ #

完全等价。

大O表示法的本质是描述当n趋近于无穷大时，算法开销的上界趋势。当n足够大时，常数项（比如这里的+1）对整体增长趋势的影响可以完全忽略——比如n=100万时，log₂(n)≈20，加1之后是21，和20的增长速率没有区别。

按照大O的规则，所有常数项都会被忽略，因为它们不会改变“随着n增大，开销的增长快慢”。类似的，O(n + 100)等价于O(n)，O(2log n)等价于O(log n)，所以O(log n +1)和O(log n)是同一个复杂度级别。

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