以下算法的时间复杂度是多少？

谁能告诉我这个算法的时间复杂度是多少？ 请记住：第二种方法（findMax） – 基于它获得的索引在数组上运行，意味着方法（findMax）不会每次都在所有数组上运行。 我认为这个算法的时间复杂度是O（n），但也许我错了。

public class Q2 { public static int[] replace(int []a) { for(int i = 0; i < a.length; i++ ){ if(i == a.length-1){ a[i] = 0; } int maxSubArry = findMax(a,i); swap (a, i, maxSubArry); } return a; } public static int findMax (int[]a, int i) { // i = i +1; int tmp = 0; for(i = i +1; i tmp) tmp = a[i]; } return tmp; } public static void swap(int[]a, int i, int maxSubArry) { int temp = a[i]; a[i] = maxSubArry; a[i+1] = temp; } } 

Answer 1

你的replace方法更像是冒泡排序算法，算法复杂度为O(n*n) 。

并且 findMax的初始值应为Integer.MIN_VALUE 。 并且if语句在replace是不必要的。

 public static int[] replace(int[] a) { for (int i = 0; i < a.length-1; i++) { swap(a, i, findMax(a, i)); } return a; } public static int findMax(int[] a, int i) { int tmp = Integer.MIN_VALUE; for (i = i + 1; i < a.length; i++) { if (a[i] > tmp) tmp = a[i]; } return tmp; } 

Answer 2

您可以根据示例进行计算。 假设传递给replace（）的数组有10个元素（n = 10）。 因此，replace（）内部的循环运行10次，并将调用findMax 10次。 因为findMax中的循环只会从i + 1开始运行，所以它基于十个方法调用运行的确切次数是（9-i）次：

  outer i | inner loop | number of loops ======================================= 0 | from 1 to 9 | 9 1 | from 2 to 9 | 8 ... | ... | ... 8 | from 9 to 9 | 1 9 | no loop | 0 

所以你的内环数的公式是9 + 8 + 7 + … + 1 = 45.这大约是1/2n²，并且比n更加清晰（在本例中我们假设为10）。 由于大写符号将忽略常数值，我们可以将1/2放在一边，简单地说复杂度为O（n²）。

Answer 3

总复杂度为O（n * n）。对于方法findMax（int [] a，int i），在最坏的情况下，它将采用O（n）的复杂度，因为在最坏的情况下，它将搜索0到最后一个元素作为Max元素最后出现。

Answer 4

弄清楚这样的算法运行时间的最简单方法是注意到findMax 至少运行了一半的数组，至少有一半的元素 （前半部分）。

在数学中说同样的事情：让T（N）是findMax内部循环运行的总次数：

T（N）> = 0.5N * 0.5N

⇒T（N）> =0.25N²

因此，该算法的运行时间至少为O（N 2） 。

然后请注意， findMax 最多会为其所有元素运行整个数组，这意味着运行时间最多为 O（N²） 。