5

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

我以这种方式解决了它：

 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”数字替换它到数组中。然后，我第二次调用最大的方法。

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

4

3 回答 3

11

该算法的时间复杂度为O(n)。

每个递归调用的复杂度实际上是：

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

很容易看出（通过归纳1）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

（检查底座留作读者练习）

于 2013-07-12T18:37:02.600 回答
3

算法的复杂度将被测量为O(n)。

但真正的答案是，你的算法比它需要的更复杂，在机器资源方面也更昂贵。就有人阅读您的代码并弄清楚它在做什么而言，它的成本要高得多。

您的算法的复杂性实际上应该是：

public static int sumOfTwoLargestElements(int[] a) {

    //TODO handle case when argument is null,
    //TODO handle case when array has less than two non-null elements, etc.

    int firstLargest = Integer.MIN_VALUE;
    int secondLargest = Integer.MIN_VALUE;
    for (int v : a) {
        if ( v > firstLargest ) {
            secondLargest = firstLargest;
            firstLargest = v;
        } else if ( v > secondLargest ) secondLargest = v;
    }
    //TODO handle case when sum exceeds Integer.MAX_VALUE;
    return firstLargest + secondLargest;
}
于 2013-07-12T18:51:44.167 回答
0

“最大”方法的重现是：

        _
f(n) = !
       !  1        n = 1
       !  2f(n/2)  n >=2 
       !_

If we experiment some few cases, we notice that 

f(n) = 2^log(n)   When n is power of 2       Rq:Log base 2

Proof:

By induction,

f(1) = 2^log(1) = 2^log(2^0) = 1

We suppose that f(n) = 2^log(n)=n

We show f(2n) = 2^log(2n)= 2n^log(2)=2n

f(2n) = 2*f(2n/2) = 2*f(n)
                  = 2*2^log(n)
                  = 2^log(n) + 1
                  = 2^log(n) + log(2^0)
                  = 2^log(2n)
                  = 2n^log(2)  by log properties
                  = 2n
Then f(n) = 2^log(n)=n  When n is power of2-smooth function f(2n) < c f(n). it follows smooth function properties that **f(n) = theta of n**
于 2013-08-04T23:55:02.057 回答