先直接给你明确结论：

1. O(N/2) 完全不能简化为O(log n)，这是两个完全不同量级的时间复杂度
2. 仅遍历半数元素的for循环，时间复杂度应该简化为O(N)，而非O(log n)

为什么O(N/2)和O(log n)天差地别？ #

大O表示法的核心是描述输入规模n增长时，算法运行时间的增长趋势，我们只关注最高阶的项，并且会直接忽略常数系数：

• O(N)（包括O(N/2)、O(2N)这类带常数系数的线性复杂度）是线性增长：当n翻倍时，运行时间也会跟着翻倍。比如你遍历一半元素，n从1000变到2000，循环次数从500变到1000，完全跟着n的规模线性变化。
• O(log n)是对数增长：n翻倍时，运行时间只增加一点点。比如二分查找，n从1000变到2000，查找次数只从10次变成11次，增长极其缓慢。

这俩的增长速度差距会随着n的变大越来越夸张，绝对不能混为一谈。

为什么遍历半数元素的复杂度是O(N)？ #

大O表示法的规则里，常数系数可以被直接忽略。你的算法是遍历N/2个元素，对应的时间复杂度函数是f(n) = n/2。根据大O的定义，只要能找到一个常数c，当n足够大时，f(n) ≤ c*g(n)，那f(n)就属于O(g(n))。这里我们取c=1，显然n/2 ≤ n（当n≥0时都成立），所以f(n)属于O(N)。

举个直观的例子：不管你是遍历全部元素还是一半元素，当n变成原来的100倍时，循环次数都会变成原来的100倍（从500到50000，或者从1000到100000），都是线性的增长趋势，所以都归为O(N)。

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