1
정렬 된 정수의 배열이 있습니다. 이진 검색을 사용하여 요소를 찾을 수 있습니다. 이제 정렬 된 배열의 한 요소가 다른 요소와 교체됩니다. 교환 된 요소를 찾는 가장 좋은 방법은 무엇입니까?정렬 된 배열에서 어느 번호가 교체됩니까
A
답변
0
이러한 요소를 찾는 유일한 방법은 정규 선형 검색입니다. 기본적으로 특정 요소를 검색하지 않기 때문에 더 빨리 처리 할 수 없으며, 일부 속성을 위반 한 경우 (이 경우 주문) 위치를 검색하고 있습니다. 당신이 당신이 기본적으로 그들 모두를 검사 할 필요가있는 몇몇 위치를 검사하는 것을 건너 뛰는 것을 도울 수있는 것을 모르는 것처럼. 그래서 그것은 O (n) - 정규 선형 검색이 될 것입니다.
2
어쨌든 두 가지 요소를 모르는 경우와 교환에 "규칙"이 없기 때문에 나는이 질문을 완전히 이해할 수 있을지 확신하지 못합니다. interchanged 요소를 찾으려면 최소한 o (n)가 필요합니다. (간단한 루프로).
하나의 요소 (쌍 중 하나)를 알고 있고 다른 쌍을 찾고 싶다면. 당신이 알고있는 한 쌍의 이진 검색을하면, 그의 자리에서 다른 것을 찾을 수 있습니다.
0
선형 검색이 필요하고 최악의 시간은 선형입니다. 하지만 가장 좋은 경우는 log n 일 수 있습니다.
처음 치환 된 요소를 찾으면 정수를 알 수 있습니다. 따라서 기본적으로 두 불일치 중 하나가 일찍 발생하면 시간을 절약 할 수 있습니다.
본질적으로 이진 검색을 수행하고 전송 된 요소를 찾습니다. 너는 잘못된 방법이다. – nem035
배열을 가로 지르고 인접한 요소들을 비교한다. – talex
@ 바이너리 검색을 사용하면 잘못 배치 된 요소를 발견 할 수 없습니다. 또는 당신이 그것을 만날 수 있지만 그것이 잘못 배치 된 것을 보지 마십시오. – njzk2