算法复杂性

Question

我遇到了这个问题"实现此方法以返回给定数组中两个最大数字的总和."

我用这种方式解决了它:

 public static int sumOfTwoLargestElements(int[] a) {

     int firstLargest = largest(a, 0, a.length-1);

     int firstLarge =  a[firstLargest];
     a[firstLargest] = -1;

     int secondLargest = largest(a, 0, a.length-1);

     return firstLarge + a[secondLargest];
}

private static int largest(int s[], int start , int end){

    if (end - start == 0){

        return end;
    }


   int a = largest(s, start, start + (end-start)/2) ;
   int b = largest(s, start + (end-start)/2+1 , end);
    if(s[a] > s[b]) {

       return a;
    }else {

      return b;
    }

}

说明:我实现了一个方法'largeset'.此方法负责获取给定数组中的最大数字.

我在同一个数组中两次调用该方法.第一个调用将得到第一个最大的数字.我把它放在变量中,然后用'-1'数字替换它到数组中.然后,我第二次打电话给最大的人.

有人可以告诉我这个算法的复杂性是多少？请

Answer 1

算法的时间复杂度是O(n).

每个递归调用的复杂性实际上是:

f(n) = 2*f(n/2) + CONST

很容易看到(通过感应¹)f(n) <= CONST'*n- 因此它是O(n).

空间复杂度是O(logN)- 因为这是递归的最大深度 - 所以你O(logN)在调用堆栈上分配内存.

(1)如果你使用f(n) = 2*n*CONST - CONST你得到:

f(n) = 2*f(n/2) + CONST = (h.i.) 2*(2*CONST*n/2 - CONST) + CONST =
=  2*n*CONST - 2CONST + CONST = 2*n*CONST - CONST

(检查底座是留给读者的练习)