2

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

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

//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在第一个示例中只传递了一半数组时使用了两个，它们是否“均匀”？）

4

3 回答 3

4

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

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

  • 阅读起来更复杂，不太清楚

  • 具有奇数个元素的数组呢？

  • JVM 可能会做一些花哨的优化。边界检查（当虚拟机发现你只是在遍历整个数组时，它可能不会一直检查边界）。使用这种幻想可能会使优化器感到困惑。

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

于 2012-06-06T19:52:26.687 回答
1

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

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

于 2012-06-06T19:52:15.277 回答
0

除了您的算法不等效，因为您的第一个失败的长度为 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
}                                      // )

对于n ≥ 8，总统一成本为 4 + ⎡<em>n/2⎤·13 ≤ 14·⎡<em>n/2⎤ 。由于 14·⎡<em>n/2⎤ ≤ 28· n并且28 是一个常数因子，您的算法在 Ο( n ) 中。

或者，正如评论中已经说过的那样：n /2 · 2 仍然等于n。

于 2012-06-06T20:36:47.170 回答