Java:这个算法的优秀,平均和最差情况复杂度是多少？

Question

我想知道这个算法的复杂性.在我的情况下,良好,中等和最差都是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];
 }

Answer 1

在所有案件的复杂性(最佳/平均/最差)时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),这就是答案.

事实上 - 对于相同长度的数组,根本没有变化 - 算法具有相同的迭代次数,无论输入究竟是什么.