숫자 배열에서 최고 값과 최저 값을 결정하는 가장 좋은 알고리즘은 무엇입니까?

Question

여기에 의사 코드를 사용하고 있지만 JavaScript로 작성되었습니다. 가능한 가장 효율적인 알고리즘을 사용하여 높은 양수의 배열에 양수의 배열을 지정하려고합니다. 이것은 내가 생각해 낸 것이지만, 아마도 이것이 최선이라고 생각하지 않으며 다른 제안이 있는지 궁금해하고있었습니다. 파이썬에서

var low = 1; 
var high = 1; 
for (loop numbers) { 
    if (number > high) { 
     high = number; 
    } 
    if (low == 1) { 
     low = high; 
    } 
    if (number < low) { 
     low = number; 
    } 
} 

Answer 1

하이 및 로우를 첫 번째 요소로 초기화합니다. 임의로 "높은"또는 "낮은"숫자를 선택하는 것보다 훨씬 더 합리적입니다. 거의 가장 효율적인 알고리즘을

이

for (var i = 1, val; (val = myArray[i]) !== undefined; ++i) { 
    if (val > high) { 
     high = val; 
    } else if (val < low) { 
     low = val; 
    } 
} 

Answer 2

:

>>> seq = [1, 2, 3, 4, 5, 6, 7] 
>>> max(seq) 
7 
>>> min(seq) 
1 

Answer 3

당신은 요소의 하나가 될 수 있기 때문에 당신이 그 (것)들을 확인하기 위해 모든 요소 (n)을 통해 루프를 필요로하기 때문에 O(n) 시간에 그것을해야 최소 또는 최대. (이미 정렬되지 않은 경우)

즉, 모든 요소를 ​​반복하고 최대 및 최소 확인을 수행해야합니다.

일반적으로 정렬은 보통 O(n*log(n))입니다. 따라서 (O(n))을 통한 단일 스윕보다 느립니다.

Answer 4

목록이 이미 정렬되지 않았다고 가정 할 때, 당신이 할 수있는 최선의 방법입니다. 당신은 자신을 수행하여 비교를 저장할 수 있습니다 (의사 코드) 다음

low = +INFINITY 
high = -INFINITY 
for each n in numbers: 
    if n < low: 
     low = n 
    if n > high: 
     high = n 

이 기본적으로 당신이 할 수있는 최선 O (n) 연산입니다.

Answer 5

귀하의 예는하지만, 분명히이 모든 숫자가 적은 경우 작동하지 않습니다 : 배열 여러 번 조회 할 필요가 없도록

var myArray = [...], 
    low = myArray[0], 
    high = myArray[0] 
; 
// start looping at index 1 
for (var i = 1, l = myArray.length; i < l; ++i) { 
    if (myArray[i] > high) { 
     high = myArray[i]; 
    } else if (myArray[i] < low) { 
     low = myArray[i]; 
    } 
} 

또는, 1보다 크거나 1보다 큰 경우이 코드는 해당 경우에 작동합니다.

var low = numbers[0]; // first number in array 
var high = numbers[0]; // first number in array 
for (loop numbers) { 
    if (number > high) { 
     high = number; 
    } 
    if (number < low) { 
     low = number; 
    } 
} 

Answer 6

목록이 작은 경우 ("작은" ements) 그리고 당신은 많이하지 않습니다 ("많이"는 몇 천 번 미만입니다). 그것은 중요하지 않습니다. 최대/최소 알고리즘 최적화에 대해 걱정하기 전에 코드를 먼저 작성하여에 병목 현상을 찾으십시오.

질문에 대답 해주세요.

목록의 모든 요소를 ​​살펴 보는 방법이 없으므로 선형 검색이 가장 효율적인 알고리즘입니다. 그것은 N 시간을 필요로합니다. N은 목록에있는 요소의 수입니다. 하나의 루프에서이 모든 작업을 수행하면 max(), min() (2 * N 시간 소요)를 호출하는 것보다 더 효율적입니다. 따라서 음수를 고려하지 않아도 코드는 기본적으로 정확합니다. 여기 Perl에 있습니다.

# Initialize max & min 
my $max = $list[0]; 
my $min = $list[0]; 
for my $num (@list) { 
    $max = $num if $num > $max; 
    $min = $num if $num < $min; 
} 

첫 번째 요소와 마지막 요소를 정렬 한 다음 잡는 것이 가장 효율적이지 않습니다. N * log (N) 여기서 N은 목록의 요소 수입니다.

가장 효율적인 최소/최대 알고리즘은 요소가 목록에 추가되거나 제거 될 때마다 최소/최대가 다시 계산되는 알고리즘입니다.결과적으로 결과를 캐싱하고 매번 선형 검색을 피할 수 있습니다. 이 시간을 소비 한 시간은 목록이 변경된 횟수입니다. 그것은 대부분 M 시간입니다. M은 몇 번이나 호출해도 변경 횟수입니다.

이렇게하려면 요소를 순서대로 유지하는 검색 트리를 고려해보십시오. 해당 구조에서 최소/최대 값을 얻는 것은 사용하는 트리 스타일에 따라 O (1) 또는 O (log [n])입니다.

Answer 7

내가 제안할만한 최적화는 루프 자체를 최적화하는 것입니다. 자바 스크립트에서 카운트하는 것보다 카운트 다운하는 것이 빠릅니다.

Answer 8

여전히 O (n) 알고리즘이지만 인접한 요소를 먼저 쌍으로 비교 한 다음 더 작은 값과 최소값을 비교하면 25 % 더 빠릅니다 (비례 상수는 3/2와 2가됩니다). 최대치까지. ++ 나 자바 스크립트를 모르겠지만, 여기은 C :

std::pair<int, int> minmax(int* a, int n) 
{ 
    int low = std::numeric_limits<int>::max(); 
    int high = std::numeric_limits<int>::min(); 

    for (int i = 0; i < n-1; i += 2) { 
    if (a[i] < a[i+i]) { 
     if (a[i] < low) { 
     low = a[i]; 
     } 
     if (a[i+1] > high) { 
     high = a[i+1]; 
     } 
    } 
    else { 
     if (a[i] > high) { 
     high = a[i]; 
     } 
     if (a[i+1] < low) { 
     low = a[i+1]; 
     } 
    } 
    } 

    // Handle last element if we've got an odd array size 
    if (a[n-1] < low) { 
    low = a[n-1]; 
    } 
    if (a[n-1] > high) { 
    high = a[n-1]; 
    } 

    return std::make_pair(low, high); 
} 

Answer 9

var numbers = [1,2,5,9,16,4,6]; 

var maxNumber = Math.max.apply(null, numbers); 
var minNumber = Math.min.apply(null, numbers); 

Answer 10

nickf의 알고리즘이 작업을 수행하는 가장 좋은 방법은 아닙니다. 최악의 경우, nickf의 알고리즘은 2n-2의 합계에 대해 숫자 당 2 개의 비교를 수행합니다.

우리는 공정한 비트를 더 잘 수행 할 수 있습니다. 두 요소 a와 b를 비교할 때 a> b이면 a는 min이 아니며 b는 최대가 아님을 압니다. 이 방법으로 가능한 모든 정보를 사용하여 최대한 많은 요소를 제거합니다. 단순화를 위해 우리는 짝수 개의 요소를 가지고 있다고 가정합니다.

쌍으로 그들을 브레이크

: (A1, A2), (A3는 A4) 등

, 그들을 비교 승자와 패자의 집합으로 그들을 파괴 -이 N 소요/2는 우리에게 두 가지를 제공 비교 크기 n/2 세트. 이제 승자의 최대 수와 패자의 수를 구하십시오.

위에서부터 n 개 요소의 최소 또는 최대 값을 찾는 데는 n-1이 필요합니다. 따라서 런타임은 다음과 같습니다 : n/2 (초기 비교) + n/2-1 (최대 승자) + n/2-1 (분실자 분) = n/2 + n/2 + n/2 -2 = 3n/2 - 2. n이 홀수 인 경우 각 세트에 요소가 하나 더 있으므로 런타임은 3n/2가됩니다.

사실 우리는 이것이 이 문제는 모든 알고리즘에 의해 해결 될 수 있습니다.

예 :

는, 8, 1, 3, 2, 5, 우리의 배열이 1 쌍으로 4 분할을 가정하자 : (1,8) (2,3) (1,5)를, (4, -). 비교하십시오. 우승자는 (5, 3, 8, 4)입니다. 패자는 (1, 2, 1, 4)입니다. 수상자를 스캔

는 패자를 스캔 8. V8에 진짜, 드류 홀의 알고리즘이 nickf 년대의 시간의 2/3에서 실행에서 예상대로,이 조각을 시도 1.

Answer 11

을 제공합니다 제공합니다. 루프 카운트를 다운으로하지 않고 시간을 약 59 %로 줄입니다 (구현에 따라 다르지만). 가볍게 테스트 한 것 :

var A = [ /* 100,000 random integers */]; 

function minmax() { 
    var low = A[A.length-1]; 
    var high = A[A.length-1]; 
    var i, x, y; 
    for (i = A.length - 3; 0 <= i; i -= 2) { 
     y = A[i+1]; 
     x = A[i]; 
     if (x < y) { 
      if (x < low) { 
       low = x; 
      } 
      if (high < y) { 
       high = y; 
      } 
     } else { 
      if (y < low) { 
       low = y; 
      } 
      if (high < x) { 
       high = x; 
      } 
     } 
    } 
    if (i === -1) { 
     x = A[0]; 
     if (high < x) { 
      high = x; 
     } else if (x < low) { 
      low = x; 
     } 
    } 
    return [low, high]; 
} 

for (var i = 0; i < 1000; ++i) { minmax(); } 

하지만 사람은 꽤 추합니다.

Answer 12

자바 스크립트 배열에는 비교에 사용할 함수를 받아들이는 원시 정렬 함수가 있습니다. 숫자를 정렬하고 머리와 꼬리를 가져 와서 최소값과 최대 값을 얻을 수 있습니다.기본적으로

var sorted = arrayOfNumbers.sort(function(a, b) { return a - b; }), 
    ,min = sorted[0], max = sorted[sorted.length -1]; 

은 정렬 방법은 사 전적으로 (사전 순서) 정렬 그래서 당신은이 숫자 정렬을 얻기 위해 사용하는 함수에 전달해야하는 이유입니다. 전달한 함수는 정렬 순서를 결정하기 위해 1, -1 또는 0을 반환해야합니다.

// standard sort function 
function sorter(a, b) { 
    if (/* some check */) 
    return -1; // a should be left of b 
    if (/*some other check*/) 
    return 1; // a should be to the right of b 
    return 0; // a is equal to b (no movement) 
} 

숫자의 경우 첫 번째 매개 변수에서 두 번째 숫자를 빼기 만하면 순서를 결정할 수 있습니다. 이 알고리즘은 O (N) 및 요소를 저장하는 데 필요한 더 이상 추가 메모리 작동

var numbers = [5,8,123,1,7,77,3.14,-5]; 

// default lexicographical sort 
numbers.sort() // -5,1,123,3.14,5,7,77,8 

// numerical sort 
numbers.sort(function(a, b) { return a - b; }) // -5,1,123,3.14,5,7,77,8 

Answer 13

...

enter code here 
int l=0,h=1,index,i=3; 
    if(a[l]>a[h]) 
       swap(&a[l],&a[h]); 
    for(i=2;i<9;i++) 
    { 
           if(a[i]<a[l]) 
           { 
             swap(&a[i],&a[l]); 
           } 
           if(a[i]>a[h]) 
           { 
              swap(&a[i],&a[h]); 
           } 
    } 
    printf("Low: %d High: %d",a[0],a[1]); 

Answer 14

그것을 spread syntax를 사용하여 ES6 방법 수행 :

var arrNums = [1, 2, 3, 4, 5]; 
Math.max(...arrNums) // 5 
Math.min(...arrNums) // 1