算法复杂度

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

(检查基数留给读者作为练习)