정렬되지 않은 목록에서 요소를 찾는 가장 효율적인 방법은 무엇입니까?

Question

배열에 정렬되지 않은 목록이 있으면 x보다 작은 요소의 수를 찾기 위해 반드시 선형 시간이 필요합니까? 그렇다면 왜?

Answer 1

예. 모든 임계 값이 지정된 임계 값보다 작은 지 알기 위해서는 모든 숫자를 최소한 한 번 검사해야합니다. 숫자가 정렬되지 않으면 그 숫자에 대해 추측 할 수있는 것이 없습니다.

Answer 2

예 적어도 선형 시간이 필요합니다. 요소가 검사하지 않고 x보다 작은 지 여부를 알 수있는 방법이 없기 때문에 모든 요소를 ​​한 번 확인해야합니다.

먼저 정렬 한 경우 요소가 x보다 큰 경우 즉시 중지 할 수 있습니다.

Answer 3

무제한의 프로세서를 허용하는 경우 거의 일정한 시간 내에 문제를 해결할 수 있습니다. 결과를 연결하는 것은 간단합니다. 고정 된 크기의 청크로 배열을 분할하고 각 청크를 별도의 프로세서에서 처리하기 만하면됩니다. 우리는 하나의 프로세서에 대해 이야기하는 경우

난 당신이 선형 시간이 필요 말하고 싶지만 :

• 당신은 각 요소를 검사 할 필요가 맞는 경우 술어는 결과에 넣어.
• 정렬이나 유사하면 도움이되지 않습니다. 다시 한 번 적어도 각 요소를 검사해야하기 때문입니다.