어떻게이 알고리즘을보다 효율적으로 만들 수 있습니까?

모든 가능한 값의 합계를 포함하는 2D 배열을 생성하는 알고리즘이 있습니다. 예를 들어, 배열 [1,5,8,4,5]의 경우 2D 배열 sums[1][3]은 원래 배열 (17)의 인덱스 1-3의 합계를 반환해야합니다. 나는 큰 O의 측면에서 효율성이 O (N)라고 믿습니다. 이 알고리즘을 더 효율적으로 만들 수있는 방법이 있습니까?어떻게이 알고리즘을보다 효율적으로 만들 수 있습니까?

public static int[][] sum(int[] values){ 
    int[][] sums = new int[values.length][values.length]; 
    for(int x = 0; x < values.length; x++){ 
     int total = 0; 
     for(int y = x; y < values.length; y++) { 
      total += values[y]; 
      sums[x][y] = total; 
     } 
    } 
    return sums; 
}

출처

2016-11-10 Top Cat

'N^2'크기의 표를 채워야합니다. 'O (N^2) 미만으로 세상에서 어떻게 할 수 있니? '?? –

비슷한 질문입니다. O (nlog (n))에서 수행 할 수 있습니다. http://stackoverflow.com/a/37907843/3160529 – Shubham

그게 바로 내가 궁금해 한 것입니다. 강의 슬라이드의 질문이며 그것을 이해하려고 노력했습니다. –

당신은 접두사 합계 배열 O(n) 시간과 공간에서이 문제를 해결 할 수 있습니다

array = [1, 5, 8, 4, 5] 
prefixes = [1, 6,14,18,23] 

sums(1,3) = prefixes[3] - prefixes[0] = 18 - 1 = 17

출처

2016-11-10 19:53:53

이것은 결코 질문에 대답하는 것이 아닙니다. 'sums (1, 3) = 배열 [1] + 배열 [3]'. 그래서 요점은 무엇입니까? 빼기로 더하기를 바 꾸었습니다. 2D 배열을 채우지 않습니다. –

@EugeneSh. 당신의 의견에 감사드립니다. 'array [1] + array [3]'가'9'와 같지 않습니까? OP는'sum [1] [3]'은'array [1] + array [2] + array [3]'의 합계를 반환해야한다는 것을 의미한다고 생각합니다. 이것은'5 + 8 + 4 = 17'입니다. 내가 이해하는 한, 질문은 "어떻게이 알고리즘을보다 효율적으로 만들 수 있습니까?"입니다. 내 대답은 그 방법 중 하나를 제안한다고 생각합니다. –

답변은 작동하지만 필요한 것은 아닙니다. 내가 찾고있는 것은'arr [1] [3]'이 인덱스 1-3의 모든 값의 합을 반환하도록 2 배열을 생성하는 알고리즘입니다. 이 대답은 합계를 계산하는 방법을 사용합니다 (그러나 이것은 불가능할 수도 있음). –

계산 prefix 합을 다음과 같은 방법으로 :

귀하의 요청으로 당

public static int[] sum(int[] values){ 
    int[] prefix_sums = new int[values.length]; 
    prefix_sums[0] = values[0]; 
    for(int x = 1; x < values.length; x++){ 
     prefix_sums[x] = prefix_sums[x-1] + values[x]; 
    } 
    return prefix_sums; 
}

, 색인 x에서 색인 y (0 기반 색인 생성)의 합계를 찾고 싶다면 다음 방법을 사용하십시오.

if(x==0) 
    result = prefix_sums[y]; 
else 
    result = prefix_sums[y] - prefix_sums[x-1];

희망이 있습니다. !!!

출처

2016-11-11 05:25:30

어떻게이 알고리즘을보다 효율적으로 만들 수 있습니까?

답변

관련 문제