Złożoność algorytmu

Question

Mam problem "Zaimplementuj tę metodę, aby zwrócić sumę dwóch największych liczb w danej tablicy."

postanowiłem go w ten sposób:

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

} 

Objaśnienie: I wdrożone metoda 'largeset'. Ta metoda jest odpowiedzialna za uzyskanie największej liczby w danej macierzy.

Ja nazywam czasy przeciągnięcia metody w tej samej tablicy. Pierwsze wywołanie otrzyma pierwszą największą liczbę. Odkładam ją na zmienną i zastępuję ją przez liczbę "-1" w tablicy. Następnie, po raz drugi nazywam największą medhodę.

Ktoś może mi powiedzieć, jaka jest złożoność tego algo? proszę

Answer 1

Złożoność czasowa algorytmu to O(n).

złożoność każdego wywołania rekurencyjnego jest faktycznie:

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

Łatwo jest zobaczyć (przez indukcję), które f(n) <= CONST'*n - i dlatego jest O(n).

Złożoność przestrzeni to O(logN) - ponieważ jest to maksymalna głębokość rekursji - dzięki czemu można przydzielić pamięć O(logN) na stosie wywołań.

---

(1) Jeśli używasz f(n) = 2*n*CONST - CONST otrzymasz:

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 

(Sprawdzanie bazy jest pozostawiamy jako ćwiczenie dla czytelnika)

Answer 2

Złożoność algorytmu byłaby mierzona jako O(n).

Ale prawdziwą odpowiedzią jest to, że twój algorytm jest DROŻniejszy, bardziej złożony i droższy pod względem zasobów maszyny niż powinien. I jest DROŻO droższy jeśli chodzi o kogoś, kto czyta twój kod i zastanawia się, co robi.

Złożoność algorytmu powinien być naprawdę na porządku:

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

Moim celem jest wdrożenie algorytmu dla „największa” z złożoności mniej niż O (n). Dlatego nie chciałem zrobić pętli for. Dzięki za odpowiedzi :)

Answer 4

nawrotu dla „Największy” metody to:

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