Сложность алгоритма

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 

(Проверка базы будет оставлено в качестве упражнения для читателя)

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; 
} 

Answer 3

Моя цель состоит в том, чтобы реализовать алгоритм «самый большой» со сложностью меньше, чем O (N). Вот почему я не хотел делать цикл for. Спасибо за ваши ответы :)

Answer 4

рекуррентности для «Самой большой» методы:

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