원패스 알고리즘

One-pass algorithm

컴퓨팅에서 원패스 알고리즘 또는 싱글패스 알고리즘은 입력을 정확히 한 [1]번 읽는 스트리밍 알고리즘입니다.무한 버퍼링 없이 아이템을 순서대로 처리함으로써 블록이 입력 버퍼로 읽혀지고 처리되며 프로세스 [2]단계별로 출력 버퍼로 이동합니다.원패스 알고리즘은 일반적으로 O(n)('빅 O' 표기법 참조) 시간이 필요하며 O(n) 스토리지(일반적으로 O(1)보다 작습니다. 여기서 n은 입력 [3]크기입니다.원패스 알고리즘의 예는 부분적으로 관측 가능한 마르코프 결정 과정이다.[4]

원패스 알고리즘으로 해결할 수 있는 문제의 예

입력으로 지정된 목록:

  • 요소의 수를 세다.

번호 목록 지정:

k개 기호 알파벳의 기호 목록이 미리 주어져 있습니다.

  • 각 기호가 입력에 표시되는 횟수를 카운트합니다.
  • 빈도가 가장 높거나 낮은 요소를 찾습니다.
  • 기호의 순서에 따라 목록을 정렬합니다(기호의 수가 제한되어 있기 때문에 가능).
  • 주어진 기호의 두 모양 사이의 최대 간격을 찾습니다.

원패스 알고리즘으로 해결할 수 없는 문제의 예

입력으로 지정된 목록:

  • 끝에서 n번째 요소를 찾습니다(또는 목록에 n개 미만의 요소가 있는 것으로 보고합니다).
  • 목록의 중간 요소를 찾습니다.단, 이는 2개의 패스로 해결할 수 있습니다.합격 1은 요소를 카운트하고 합격 2는 가운데 요소를 선택합니다.

번호 목록 지정:

  • 중앙값을 구합니다.
  • 모드를 찾습니다(제한된 알파벳에서 가장 빈번한 기호를 찾는 것과 동일하지 않습니다).
  • 목록을 정렬합니다.
  • 평균보다 크거나 작은 항목의 수를 셉니다.단, 이것은 2개의 패스를 사용하여 일정한 메모리에서 실행할 수 있습니다.통과 1은 평균을 구하고 통과 2는 카운트를 수행합니다.

위의 2패스 알고리즘은 스트리밍 알고리즘이지만 1패스 알고리즘은 아닙니다.

레퍼런스

  1. ^ Schweikardt, Nicole. "One-Pass Algorithm" (PDF). Retrieved 2021-07-01.{{cite web}}: CS1 maint :url-status (링크)
  2. ^ Pollett, Chris (2005-03-14). "One and Two Pass Algorithms" (PDF). Retrieved 2021-07-01.{{cite web}}: CS1 maint :url-status (링크)
  3. ^ Schweikardt, Nicole (2009), LIU, LING; ÖZSU, M. TAMER (eds.), "One-Pass Algorithm", Encyclopedia of Database Systems, Boston, MA: Springer US, pp. 1948–1949, doi:10.1007/978-0-387-39940-9_253, ISBN 978-0-387-39940-9, retrieved 2021-04-13
  4. ^ "Sondik's One-Pass Algorithm". www.pomdp.org.
Stub icon

이 컴퓨터 과학 기사는 촌스럽다.위키피디아를 확장함으로써 위키피디아를 도울 수 있습니다.