java是另一个时间复杂性问题

Question

我已经解决了这些问题，所以我不是在寻找一个直截了当的答案。我正在寻找有关我是否正确操作的指导，如果没有，可能需要一些关于我不正确原因的解释。：）

所以我有两个问题。我已经在为什么我得到我的答案中评论了我的逻辑。如果有人能证明我做得对吗

public static Integer findTripleB(int[] anArray) {
//Method Variable: n
       if (anArray.length <= 2) {
          return false;
       }                //Time Complexity: 1
       // use insertion sort to sort anArray
       for (int i = 1; i < anArray.length; i++) {//TC 1+(n+1)+n
          // insert anArray[i]
          int j = i-1; //TC 1
          int element=anArray[i]; //TC 1
          while (j >= 0 && anArray[j] > element) {//TC log(n)
             anArray[j+1] = anArray[j]; //TC 1
             j--; //TC 1
          }
          anArray[j+1] = element; //TC 1
       } //Total TC: (2n+2)(1+1+log(n)(2)) = (2n+2)(2+2log(n)) = 4n+(2log(n))(2n)+4+4log(n)
       // check whether anArray contains three consecutive 
       // elements of the same value
       for (int i = 0; i < anArray.length-2; i++) {//TC 1+n-1+n
          if (anArray[i] == anArray[i+2]) {//TC 1
             return new Integer(anArray[i]);//TC 1
          }
       }//Total TC: (2n)(2) = 4n
       return null;//TC 1
        }   //TOTAL TIME COMPLEXITY: 5+8n+4nlog(n)+4log(n)

为了获得最佳的时间复杂度，我得到了O（1），因为如果数组是>；=长度2，它将返回。在最坏的情况下，我得到了O（n*log（n））

对于一个更简单的问题

boolean findTripleA(int[] anArray) { //Method Variable: n
   if (anArray.length <= 2) {
      return false;//TC 1
   }//TC 1
   for (int i=0; i < anArray.length; i++) {//TC 1+n+1+n
      // check if anArray[i] occurs at least three times 
      // by counting how often it occurs in anArray
      int count = 0;//TC 1
      for (int j = 0; j < anArray.length; j++) {//TC 1+n+1+n
         if (anArray[i] == anArray[j]) {
            count++;
         }//TC 1
      }//Total TC: 2n+2
      if (count >= 3) {
         return true;
      }//TC 1
   }//Total TC: (2n+2)(1+2n+2+1) = (2n+2)(2n+4) = 4n2+12n+8
   return false;//TC 1
}//TOTAL TIME COMPLEXITY: 4n2+12n+9

对于最佳情况，与第一个问题O（1）相同。对于最坏的情况，O（n^2）

这些是否正确？如果不正确，原因为何？再说一遍，我不是在寻找答案。我在寻找指导，因为我的教授似乎不想帮忙，而班上其他人也一样困惑

Answer 1

一般来说，试图超越数量级是没有意义的。如果有一个N平方项，你可以称它为O（N**2），保持不变。如果你想更准确，我建议在上面运行一个分析器。。。需要注意的是，热点优化、JIT不确定性和GC时间共同导致在Java中很难对性能进行精确测量

Answer 2

对于第一个示例，这里有几点：

算法的复杂性分析不是关于算法的单一情况（例如数组大小为2），而是关于算法在任意大小输入的最佳/最差/平均情况下所需的时间（任何给定大小的数组）。从技术上讲，当n（输入的大小）趋于无穷大时，您可以对行为进行分析。因此，循环前的if语句不会影响算法的渐近最佳情况性能

插入排序的最坏情况是O（n^2）。如果输入数组已按相反顺序排序，则可以获得这种时间。所以你对第一个案例的结论是错误的。所以我不必写一个冗长的描述来说明为什么会这样，这里有一个解释来解释为什么它是来自here的O（n^2）：

It's not entirely clear, however, how much longer the inner while loop will take if we have twice the array size. After all, it doesn't go through the entire array. In fact, on average, it only goes through about half the array, as our diagram here illustrates, sometimes less, early in the sort, and sometimes more, later in the sort, but half of the array on average. And even then it doesn't usually go all the way down to index 0. It will, again on average, scan through about half the sorted set before finding the right spot. So, it's reasonable to estimate that the inner-while loop must iterate through ¼ of the array for each time through the outer for-loop. The sorted set it must search averages half the size of the array, and on average it must hunt through half the sorted set before finding the right spot.

But, even if it's just ¼ of the array, that will still double if the array size doubles ¼ of 1000 is 250, and ¼ of 2000 is 500, twice as much. And so when the array size doubles, the inner while loop takes twice as long on average, and it must be performed twice as many times by the outer for loop. Thus insertion sort takes 4 times as long to run when the array size doubles. It's run time is proportional to n^2, and we say it is O(n^2).

最好的情况是，你也错了。即使它“刚刚返回”，您仍然要经历与数组中元素数量成比例（实际上，相等）的大量比较（即使它只有2个元素）。因此，最好的情况是O（n）比较，因为您必须检查每个元素是否处于正确的位置，但是O（1）交换（如果它已经按正确的顺序排序，并且没有任何地方可以交换）

此外，在代码中，在同一方法的一个位置返回布尔值，在另外两个位置返回整数。这没有道理

希望一切都清楚了