使用两个 if 的半数组循环的时间复杂度与使用一个 if 的全数组循环的时间复杂度相同吗？

Question

我想知道下面代码示例的两个变体在技术上是否具有相同的运行时复杂性。

例如（为了说明问题，假设字符串的长度是偶数）：

//counting how many times char 'c' appear in the string s

String s = "ascdwcccdweccaaa"; //the "array", contain char 'c' 6 times

int counter = 0; //times char 'c' appear in the string

for(int i=1; i <= s.length()/2; i++)
    {
    if(s.charAt(i-1) == 'c')
        counter++;
    if(s.charAt(s.length()-i) == 'c')
        counter++;
    }

与此相比...

for(int i=0; i < s.length(); i++)
    if(s.charAt(i) == 'c')
        counter++;

第一个示例使用索引从数组的末尾和开头进行检查，直到到达数组的中间（据说是O(n/2)）

而第二个示例是严格检查数组中从头到尾的所有字符（据说是O(n)）

在第一个示例中，我需要使用两个ifs，而在第二个示例中，我需要使用一个if。

这两个代码在时间复杂度上技术上是否相同？（鉴于我ifs在第一个示例中仅传递一半数组时使用了两个，它们是否“均匀”？）

Answer 1

你们的两个程序都具有完全相同的O(n)复杂性。事实上O(n/2)等于，O(n)因为它是相同的顺序。但即使考虑到这一点：您执行两倍工作量的迭代次数也减少了两倍。总计是一样的。

所以程序具有相同的复杂性。然而第一个有几个缺点：

• 阅读起来比较复杂并且不太清晰

• 元素个数为奇数的数组又如何呢？

• JVM 可能会做一些奇特的优化。边界检查（当虚拟机发现您只是迭代整个数组时，它可能不会一直检查边界）。使用这种花哨可能会让优化器感到困惑。

话虽这么说，你在尝试优化代码的同时，却让你的代码变得更难阅读、不正确，而且可能更慢。