-4

我想知道这个算法的复杂性。在我的情况下，好、中等和最差都是 O(n^2)

public char getModa(char[] a){
   int ii[] =new int[a.length];
   char[] t= new char[a.length];

   for(int i=0;i<a.length;i++){
    for(int j=0;j<a.length;j++){
       if(a[j]==a[i]){ 
          ii[i]++;
          t[i]=a[j];
       }
     }
   }
   int cc=0;
   for(int i=0;i<ii.length;i++){
     if(ii[i]>ii[cc]) cc=i;
   }
   return a[cc];
 }
4

4 回答 4

5

所有情况的复杂性（最佳/平均/最差）是O(n^2)，瓶颈是 中的双重迭代(i,j)。range([0,a.length),[0,a.length))

澄清为什么确实如此O(n^2)，而不是O(n^3)像人们想象的那样 - 因为最后一个循环没有“嵌套”在瓶颈侧，所以 3 个循环的复杂性基本上是O(n^2+n)，但是因为O(n^2+n) = O(n^2)，这就是答案。

事实上 - 对于相同长度的数组，根本没有变化 - 该算法具有相同数量的迭代，无论输入到底是什么。

于 2013-01-23T12:41:56.997 回答
1

嵌套 for 循环内的代码运行 (a.length)^2 次，最后一个 for 循环内的代码运行 ii.length = a.length 次。所以，我们总共有 (a.length)^2 + a.length 迭代，结果为 O(a.length^2)。

迭代的数量（以及复杂性）仅取决于 a 的大小，而不是其中的值。因此，在最好和最坏的情况下都是一样的。

于 2013-01-23T12:45:06.647 回答
1

你的复杂性是O(N^2)

如果使用Hash TableO(N)可能会复杂地解决类似的问题。

于 2013-01-23T12:56:31.943 回答
0

for 循环直接取决于数组的长度a。

所以O(n*n)在所有情况下都是如此。

最后一个 for 循环不会影响程序的复杂性，因为它已经O(n*n)

于 2013-01-23T12:44:41.007 回答