算法复杂度

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‘数字。然后，我第二次调用最大的medhod。

有人能告诉我这个算法有多复杂吗？请

Answer 1

算法的复杂度将以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;
}

Answer 2

“最大”方法的重现率为：

        _
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**