2013-04-05 13 views
2

정수 배열을 감안할 때 배열의 작은 숫자 뒤에 큰 숫자가 표시되도록 두 요소 간의 최대 차이를 찾아야합니다. 간단한 접근 방식을 사용하여 차이를 가져 왔습니다. 최소 수는두 요소 사이의 최대 차이

2.Minimum 번호 지금까지 방문 2 일

1.Maximum 차이의 트랙을 유지하여 지금까지 발생했습니다.

int min_element=arr[0]; 
    int diff=arr[1]-arr[0]; 
    for(i=1;i<n;i++) 
    { 
     if(arr[i]-min_element>diff) 
      diff=arr[i]-min_element; 
     if(arr[i]<min_element) 
      min_element=arr[i]; 
    } 
    return diff; 

이 문제를 해결하기위한 더 나은 방법이 있습니까?

+3

* 작업 * 코드가있어서 비용 회수가 필요하므로 [코드 검토] (http://codereview.stackexchange.com/)에 대한 질문으로 간주 할 수 있습니다. – Mike

+3

가지고 계신 분이 좋습니다. 당신은 일정한 요소에 의해 속도를 높이기 위해 다양한 트릭을 사용할 수 있지만, 일정한 요소 (단지 구현이 달성되는 Ω (n) 시간이 필요함)에 의해서만 가능할 수 있습니다. 이것이 프로그램의 중요한 성능 병목 현상이 아니라면 컴파일러에 최적화가 설정되어 있는지 확인하고 다음 문제로 넘어갑니다. –

+1

Nitpick : 당신은'arr [1]'이'arr [0]'보다 큰지 확인하지 않습니다. 데이터가 역순으로 정렬되지 않는 한 자체 정렬해야하지만 경계 조건 (요소가 두 개 뿐이지 만 순서가 증가하지 않는 경우)을 고려해야합니다. –

답변

3

여러분의 알고리즘은 일정한 요소까지 최적화되어 있습니다.

n의 배열을 읽는 데는 Ω(n)이 필요합니다. 귀하의 알고리즘은 O(n)입니다.