第二个嵌套循环的时间复杂度只有一半

Question

我有以下代码。我看到的代码的运行时间是 O(n^2)，因为它从 1, ..., n-1 运行，所以它们的总和是 O(n^2)。我知道运行时间确实是 (n-1)(n/2)，所以内部循环从 1 运行到 n/2，但正如我所见，它从 1 运行到n-1。你能说明为什么内循环最多运行 (n/2) 次吗？

public static void method2(int[] array, int n)
{
  for (int index = 1; index <= n - 1; index++){
    privateMethod2(array[index], array, 0, index - 1);
  } // end method2
public static void privateMethod2(int entry, int[] array, int begin, int end)
{
  int index;
  for (index = end; (index >= begin) && (entry < array[index]); index--){
    array[index + 1] = array[index];
    array[index + 1] = entry;
} // end privateMethod2

Answer 1

在最坏的情况下，内循环平均运行 n/2 次。在第一次迭代中，它只从索引 0 到索引 0 运行一次，在第二次迭代中，它从索引=1 到索引=0 运行 2 次，在最后一次迭代中它运行 n 次。所以它平均运行 n/2 次

第二个嵌套循环的时间复杂度只有一半

Time complexity of second nested loop is just half

java

time-complexity