java - 使用两个 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))

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

这两个代码在时间复杂度上技术上是否相同？ (考虑到当我在第一个示例中只传递一半数组时我使用了两个 if ，它们是否“均匀”？)

Answer 1

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

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

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

• 元素个数为奇数的数组怎么样？

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

话虽如此，在尝试优化代码时，您使代码更难阅读、不正确并且可能更慢。