선형 검색

이 문서에는 여러 가지 문제가 있습니다.개선을 돕거나 토크 페이지에서 이러한 문제에 대해 논의해 주십시오.(이러한 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다) 이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : '리니어 검색'– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2010년 11월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인) 이 기사는 대부분 또는 전체적으로 단일 출처에 의존하고 있습니다. 관련 토론은 토크 페이지에서 확인할 수 있습니다. 추가 출처에 인용문을 도입하여 이 기사의 개선에 도움을 주시기 바랍니다.출처 : 「선형 검색」– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2010년 11월) (이 템플릿메시지를 삭제하는 방법과 타이밍을 확인합니다)

선형 검색

학급	검색 알고리즘
최악의 경우 성능	O(n)
베스트 케이스 성능	O(1)
평균 성능	O(n/2)
최악의 경우 공간의 복잡성	O(1) 반복

컴퓨터 과학에서 선형 검색 또는 순차 검색은 목록 내의 요소를 찾는 방법입니다.일치하는 항목이 발견되거나 목록 전체가 ^[1]검색될 때까지 목록의 각 요소를 순차적으로 확인합니다.

선형 검색은 최악의 선형 시간에 실행되며 최대 n개의 비교를 수행합니다. 여기서 n은 목록의 길이입니다.만약 각 요소를 마련한 다음 검색될 가능성이 선형 검색.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac .num,.mw-parser-output.sfrac .den{의 평균 사례가 있다.디스플레이:블록, line-height:1em, 마진:00.1em}.mw-parser-output.sfrac .den{border-top:1px 고체}.mw-parser-output .sr-only{국경:0;클립:rect(0,0,0,0), 높이:1px, 마진:-1px, 오버 플로: 숨어 있었다. 패딩:0;위치:절대, 너비:1px}n+1/2 비교지만, 만약 각 요소에 대한 검색 가능성마다 차이가 평균 사건 영향을 받을 수 있다.이진 검색 알고리즘 및 해시 테이블과 같은 다른 검색 알고리즘 및 방식을 사용하면 짧은 목록을 제외한 모든 목록을 훨씬 ^[2]더 빠르게 검색할 수 있기 때문에 선형 검색은 거의 실용적이지 않습니다.

알고리즘.

선형 검색은 대상 값과 일치하는 요소를 찾을 때까지 목록의 각 요소를 순차적으로 검사합니다.알고리즘이 목록의 끝에 도달하면 검색이 정상적으로 ^[1]종료되지 않습니다.

기본 알고리즘

값 또는 레코드₀ L이 있는 n개의 요소 목록 L이 지정됩니다. L_n−1 및 목표값 T는 다음 서브루틴에서 선형 검색을 사용하여 ^[3]L 내의 목표값 T의 인덱스를 구한다.

1. i를 0으로 설정합니다.
2. L = T이면 검색이_i 성공적으로 종료됩니다. i를 반환합니다.
3. i를 1씩 늘립니다.
4. n 이면 스텝2로 넘어갑니다그렇지 않으면 검색이 정상적으로 종료되지 않습니다.

보초와 함께

위의 기본 알고리즘은 반복마다 L이 T와 동일한지_i 여부를 확인하는 것과 목록의 유효한 인덱스를 가리키는지 확인하는 두 가지 비교를 수행합니다.타겟과 같은 리스트(sentinel 값)에 추가_n 레코드 L을 추가하는 것으로, 검색 종료까지 제2의 비교를 없앨 수 있어 알고리즘의 고속화를 도모할 수 있다.대상이 ^[4]목록에 포함되지 않은 경우 검색은 초소에 도달합니다.

1. i를 0으로 설정합니다.
2. L_i = T이면 4단계로 이동합니다.
3. i를 1씩 늘리고 2단계로 이동합니다.
4. i < n 의 경우, 검색이 정상적으로 종료됩니다.i 를 반환합니다.그렇지 않으면 검색이 정상적으로 종료되지 않습니다.

정렬된 표에서

리스트가 L l₁ L 로 정렬되어₀ 있는 경우... ②_n−1 L, 검색은 L이 목표치를 초과하면 검색을_i 종료함으로써 목표물의 부재를 보다 빠르게 파악할 수 있다.이 변형에는 ^[5]대상보다 큰 감시자가 필요합니다.

1. i를 0으로 설정합니다.
2. L t T의 경우는_i 스텝4로 넘어갑니다
3. i를 1씩 늘리고 2단계로 이동합니다.
4. L = T이면 검색이_i 성공적으로 종료됩니다. i를 반환합니다.그렇지 않으면 검색이 정상적으로 종료되지 않습니다.

분석.

n개의 항목이 있는 목록의 경우 값이 목록의 첫 번째 요소와 같을 때 가장 적합합니다.이 경우 비교는 1개만 필요합니다.최악의 경우는 값이 목록에 없는 경우(또는 목록의 끝에1회만 발생하는 경우)입니다.이 경우 n개의 비교가 필요합니다.

찾는 값이 목록에서 k번 발생하고 목록의 모든 순서가 같을 경우 예상되는 비교 횟수는 다음과 같습니다.

${\displaystyle {case}n&{\mbox{if}}k=0\[5pt]\displaystyle {frac {n+1}{k+1}&{mbox{if}1\leq k\leq n.\end {case}}$

예를 들어, 찾고 있는 값이 목록에서 한 번 발생하고 목록의 모든 순서가 같을 경우 예상되는 비교 횟수는 n${\displaystyle \frac{}{}}$+ ${\displaystyle \frac{\mathrm{}}{}}$ $(\displaystyle\frac {n+1}{2$입니다.다만, 한 번 발생하는 것으로 판명된 경우에는 n - 1의 비교가 필요하며 예상되는 비교 횟수는 다음과 같습니다.

$\displaystyle \displaystyle {(n+2)(n-1)}{2n}}$

(예를 들어, n = 2의 경우 이는 1이며, 단일 if-then-then-corructure에 해당합니다).

어느 쪽이든, 점근적으로 최악의 경우 비용과 선형 검색의 예상 비용은 모두 O(n)입니다.

불균일 확률

원하는 값이 목록의 끝보다 시작 부분에 더 가까울 경우 선형 검색 성능이 향상됩니다.따라서 일부 값이 다른 값보다 검색될 가능성이 훨씬 높은 경우 목록의 선두에 배치하는 것이 좋습니다.

특히, 리스트 항목을 확률 저하순으로 배열해, 이러한 확률을 기하학적으로 분포시킨 경우, 선형 검색의 코스트는 O(1)에 불과하다.^[6]

어플

선형 검색은 일반적으로 구현이 매우 간단하며 목록에 몇 가지 요소만 있거나 순서가 지정되지 않은 목록에서 단일 검색을 수행할 때 유용합니다.

동일한 목록에서 여러 값을 검색해야 하는 경우 더 빠른 방법을 사용하기 위해 목록을 사전 처리하는 것이 일반적입니다.예를 들어 목록을 정렬하고 바이너리 검색을 사용하거나 목록에서 효율적인 검색 데이터 구조를 구축할 수 있습니다.리스트의 내용이 빈번하게 변경되는 경우, 재구성을 반복하는 것은 큰 문제가 될 수 있습니다.

그 결과 이론적으로는 다른 검색 알고리즘이 선형 검색(예를 들어 이진 검색)보다 빠를 수 있지만 실제로는 중간 크기 어레이(약 100개 항목 이하)에서도 다른 어떤 것도 사용하지 못할 수 있습니다.대규모 어레이에서는 데이터를 준비(정렬)하는 초기 시간이 많은 선형 ^[7]검색과 비슷하기 때문에 데이터가 충분히 큰 경우에만 다른 빠른 검색 방법을 사용하는 것이 좋습니다.

「 」를 참조해 주세요.

• 삼진수 검색
• 해시 테이블
• 선형 검색 문제

레퍼런스

인용문

작동하다

• Knuth, Donald (1998). Sorting and Searching. The Art of Computer Programming. Vol. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional. ISBN 0-201-89685-0