세트의 최대 값 찾기

숫자가 포인트로 증가한 다음 그 포인트 다음에 감소하는 숫자 목록이있는 경우, 세트의 크기에 관계없이 유한 한 수의 추정치가 있습니까? 그 최대 값을 찾으려면?세트의 최대 값 찾기

값 사이의 거리는 임의이고 증가하는 쪽의 값의 수는 감소하는 쪽의 값의 수와 다를 수 있습니다.

가장 좋은 방법은 무엇입니까? 요소 1을 확인한 다음 마지막 요소를 확인한 다음 그 사이의 절반을 확인하십시오. 그리고 반복할까요? 아니면 더 정교한 무언가?

이러한 알고리즘의 처리 시간은 어떻게됩니까?

2012-11-19 Peregrine

하나의 요소 대신 두 인접 요소를 고정 값과 비교하는 이진 검색을 사용할 수 있습니다. a : = 0, b : = n, i : = (a + b)/2에서 시작하여 요소 (i)와 요소 (i + 1)를 비교하십시오. e (i + 1)> e (i)를 발견하면 중단 점이 i 다음에 있음을 알고 있으므로 a : = i를 설정하십시오. e (i) < e (i-1)이면 반대가 true이고 b : = i로 설정합니다.

그러면 복잡도는 O (log n)가됩니다. 더 많은 비교가 필요하기 때문에 일반 이진 검색보다 약간 느립니다.

출처

2012-11-19 11:39:31 Gaminic

목록에있는 요소의 수를 기반으로 정렬 된 검색과 비슷한 rcursive 알고리즘을 시도해 볼 수 있습니다.

의사 코드 :

List search(int index, List listpart){ 
    if(listpart.length()==1){ // already found 
     return listpart 
    } 
    else if(listpart(index+1)>listpart(i) && listpart(index-1)<listpart(i)){ //search right part 
     List listpart_tmp = getlistpart(listpart, index, listpart.length()) 
     return search(index+(listpart.length()/4), listpart_tmp 
    } 
    else if(listpart(index+1)<listpart(i) && listpart(index-1)>listpart(i)){ //search left part 
     List listpart_tmp = getlistpart(listpart, 0, index) 
     return search(index-(listpart.length()/4), listpart_tmp 
    } 
    else if(listpart(index+1)<listpart(i) && listpart(index-1)<listpart(i)){ //found 
     return getlistpart(listpart, index, index) 
    } 
}

함수

getlistpart

지정된 인덱스 간의 원래리스트의 원소로 이루어진 목록을 반환하는 함수이다.

출처

2012-11-19 11:40:57 LuigiEdlCarno

세트의 최대 값 찾기

답변

관련 문제