算法复杂度

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”数字替换数组中的该数字。接着，我第二次调用最大值方法。

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

- fadhel ghorbel

---

您可以在第一次遍历中找到这两个数字，省略第二次遍历。这不会改变复杂度，但它会更快地运行。 :-) - assafmo

如果只是一串数字列表，那么有其他多种解决方法... 如果使用像计数排序等机制，可以在几乎不占用额外空间且O(n)时间复杂度的情况下解决。以上评论点赞加1。 - dharam

代码复杂度的真正衡量标准是未来读者花费在理解代码上的时间，当一个更简单的算法可以完成同样的工作时。递归并没有明显的好处，也不清楚为什么需要两次遍历集合。而且，当数组中最大的两个整数都小于-1时，该算法基本上是错误的（返回了错误的结果）。糟糕！ - spencer7593

Answer 1

算法的时间复杂度为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

(检查基础是留给读者的练习)

- amit

---

那么，f(0)的复杂度是负数吗？我认为复杂度应该是O(2^n * log n)。 - undur_gongor

@undur_gongor 公式显然不适用于基础或较低的值（这就是归纳法的重点，我们从某个点开始证明，以下所有情况都不适用）。基础应该是 f(1)，如前所述，留作练习。 - amit

@undur_gongor: 更确切地说，由于我们在证明中仅使用了等式，因此我们实际上表明了 f(n) 在 Theta(n) 中 - 因此 O(n) 是一个紧密的渐近界限。 - amit

Answer 2

算法复杂度会被衡量为 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;
}

- spencer7593

---

我认为你需要 if ( v > firstLargest ) { secondLargest = firstLargest; firstLargest = v }; - Rhialto supports Monica

Answer 3

'Largest' 方法的递归公式为：

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

- Fadhel Ghorbel