使用两个 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可能会在边界检查方面进行一些花哨的优化（当VM发现您只是遍历整个阵列时，它可能不会一直检查边界）。使用这种幻想可能会使优化器感到困惑。

话虽如此，你使代码更难阅读，不正确，并且可能更慢 - 同时试图优化它。

Answer 2

除了你的算法不等价，因为你的第一个失败的长度为1（1/2==0），当假设每个原子操作的统一成本为1时，你的第一个算法具有以下复杂性：

for (int i=1;                          // 1
    i <= s.length()/2;                 // 3 + ⎡n/2⎤ · ( 3
    i++) {                             //     1
    if(s.charAt(i) == 'c')             //     3
        counter++;                     //     1
    if(s.charAt(s.length()-i) == 'c')  //     4
        counter++;                     //     1
}                                      // )

总

制服成本为 4 + ⎡n/2⎤·13 ≤ n ≥ 8 的 14·⎡n/2⎤。自 14·⎡n/2⎤ ≤ 28· n 和 28 是一个常数因子，您的算法在 Ο（n） 中。

或者，正如已经说过的注释：n/2 · 2 仍然等于 n。

Answer 3

O（n） 和 O（n/2） 都具有相同的增长率（线性），因此具有相同的时间复杂度。

http://en.wikipedia.org/wiki/Big_O_notation