가장 높은 2개의 숫자 찾기 - 컴퓨터 과학

StackOverflow https://stackoverflow.com/questions/1648976

  •  22-07-2019
  •  | 
  •  

문제

숫자 목록에서 가장 높은 2개의 숫자를 찾는 알고리즘을 찾으려고 합니다.

가장 높은 숫자는 n-1 단계에서 찾을 수 있습니다. 아마도 버블 정렬의 첫 번째 단계나 해당 라인을 따라 수행하면 됩니다.나에게는 다음으로 가장 높은 숫자를 찾는 것도 평균적으로 총 1.5n번의 비교에서 찾을 수 있는 것 같습니다.

교수님은 n + log(n) 비교에서 가장 높은 2개의 숫자를 찾는 알고리즘을 작성하라는 숙제를 주셨습니다.이것이 가능합니까?어떤 아이디어나 제안이 있나요?

편집하다:내가 n + log(n)이라고 말할 때 O(n + log n)을 말하는 것이 아니라 정확히 n + log n을 말하는 것입니다.

도움이 되었습니까?

해결책

예, (n + log n) 이상으로 할 수 있습니다. 나는 답을 포기하지 않고 어떻게 당신에게 말할 수 없지만, 시도해 보자. :-)

n 숫자를 가져 가서 한 번에 쌍으로 비교하십시오. 천장 (N/2) "승자"를 가져 가서 "이진 트리처럼"반복하십시오. 질문 : 가장 큰 것을 찾기 위해서는 얼마나 많은 비교가 필요합니까? 이 "우승자"가 승리하는 사람은 몇 명입니까? 두 번째로 큰 사람은 누구에게 졌을까요? 그렇다면 두 번째로 큰 숫자를 찾기 위해서는 얼마나 많은 비교가 필요합니까?

답은 총으로 판명되었습니다 N -1 + 천장 (로그 N) -1 로그가 기본 2에 대한 비교도 비교할 수 있습니다. 또한 최악의 경우 이보다 더 잘할 수 없다는 대적 주장을 사용하여 증명할 수 있습니다.

다른 팁

편집하다:아, 어리석음으로 인해 간단한 것을 놓쳤습니다.이 솔루션은 정확하지 않지만 여전히 평균(n+log(n))이므로 여기에 유지합니다.나의 어리석음을 지적해준 ShreevatsaR에게 감사드립니다.나는 트리 검색을 고려했지만 log(n)에서 두 번째로 높은 숫자를 찾기 위해 역추적한다는 아이디어를 완전히 놓쳤습니다.

어쨌든, 열등한 알고리즘이 평균(n+log(n))보다 크지 않은 이유에 대한 증거는 다음과 같습니다.실제 생활에서는 적어도 여전히 꽤 잘 작동해야 합니다.

  • 먼저 두 번째로 높은 기록된 숫자와 비교합니다.
  • 해당 비교가 성공한 경우에만 기록된 가장 높은 숫자와 비교하십시오.

평균 n+log n임을 증명하려면 첫 번째 비교가 평균 log(n) 번만 성공한다는 것을 증명하면 됩니다.그리고 그것은 보거나 시연하기가 매우 간단합니다.

  1. P를 목록의 정렬된 버전에서 현재 두 번째로 큰 숫자의 실제 위치로 가정하고 알고리즘을 실행합니다.
  2. P>2인 경우 더 큰 숫자가 발견되면 새 P는 평균적으로 P/2를 넘지 않습니다.
  3. P=2인 경우 현재 두 번째로 큰 숫자보다 큰 숫자가 없기 때문에 첫 번째 비교가 성공할 수 없습니다.
  4. P는 기껏해야 N과 같을 수 있다
  5. 2, 3, 4에서 첫 번째 비교가 평균 log(N)회 이상 성공할 수 없다는 것을 쉽게 알 수 있습니다.

이건 어때:

for each listOfNumbers as number
    if number > secondHighest
        if number > highest
            secondHighest = highest
            highest = number
        else
            secondHighest = number

Shreevatsar가 게시 한 답변은 O (n log n) 인 것 같습니다.

첫 번째 패스 (N 운영)는 N/2 답변을 생성합니다. 반복함으로써, 당신은 N/2의 답변을 만들기 위해 N/2 작업을 수행 할 것이라고 생각합니다. 루프 로그 N 시간을 통과 할 것입니다. 이것은 병합 정렬이 매번 N 노드를 항상 처리한다는 점을 제외하고는 병합 정렬과 비슷합니다. 또한 루프 로그 N 시간을 실행합니다. 그리고이 알고리즘이 두 번째 Higest 번호를 추적하는 방법을 모르겠습니다.

Nickf는 정답을 가지고 있습니다. 최악의 경우는 목록이 정렬 될 때 2n 비교를 수행합니다. 즉, O (n).

Btw, O (N + log n)은 O (n)입니다. 순서 표기법은 최악의 경우 점근 성장을 나타냅니다.

카운팅 정렬, radix 정렬, 버킷 정렬 또는 기타 선형 시간 알고리즘을 사용하여 먼저 목록을 내림차순으로 정렬 할 수 있습니다. 그런 다음 정렬 된 목록의 첫 두 요소를 얻으십시오. 그래서 이것은 (n) + 2 = (n)을 취할 것입니다.

이 알고리즘은 각각의 가정이 있기 때문에 선형 시간으로 정렬 할 수 있습니다.

의사 코드 (본질적으로 n이 아님)

int highestNum = 0
int secondHighest = highestNum

for(i = 0; i < list.length; i++)
{
if(list[i] >= highestNum)
{
secondHighest = highestNum
highestNum = list[i]
}
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top