Độ phức tạp của thuật toán

Question

Tôi gặp sự cố này "Triển khai phương thức này để trả về tổng của hai số lớn nhất trong một mảng nhất định".

tôi giải quyết nó theo cách này:

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

} 

Giải thích: Tôi thực hiện một phương pháp 'largeset'. Phương thức này chịu trách nhiệm lấy số lớn nhất trong một mảng nhất định.

Tôi gọi phương thức kéo lần trong cùng một mảng. Cuộc gọi đầu tiên sẽ nhận được số lớn nhất đầu tiên. Tôi đặt nó sang một bên thành biến và tôi thay thế nó bằng số '-1' vào mảng. Sau đó, tôi gọi lần thứ hai là medhod lớn nhất.

Một số người có thể cho tôi biết sự phức tạp của bản ngã này là gì? vui lòng

Answer 1

Độ phức tạp của thuật toán là O(n).

phức tạp Mỗi cuộc gọi đệ quy là thực sự:

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

Nó rất dễ dàng để xem (bằng cảm ứng) mà f(n) <= CONST'*n - và do đó nó là O(n).

Độ phức tạp của không gian là O(logN) - bởi vì đây là độ sâu tối đa của đệ quy - do đó bạn phân bổ bộ nhớ O(logN) trên ngăn xếp cuộc gọi.

---

(1) Nếu bạn sử dụng f(n) = 2*n*CONST - CONST bạn nhận được:

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 

(Kiểm tra cơ sở được là trái như tập thể dục cho người đọc)

Answer 2

Sự phức tạp của thuật toán sẽ được đo là O(n).

Nhưng câu trả lời thực sự là thuật toán của bạn là WAY phức tạp hơn và tốn kém hơn về tài nguyên máy hơn mức cần thiết. Và nó tốn kém hơn về việc ai đó đọc mã của bạn và tìm hiểu xem nó đang làm gì.

Sự phức tạp của thuật toán của bạn thực sự nên vào thứ tự của:

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

Mục đích của tôi là thực hiện một thuật toán cho 'lớn' với độ phức tạp ít hơn O (n). Đó là lý do tại sao tôi không muốn làm vòng lặp for. Cám ơn câu trả lời của bạn :)

Answer 4

Các reccurence cho phương pháp 'lớn nhất' là:

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