‘complexity’ 태그의 글
2편 RSS로 구독
2편
Boyer–Moore 과반수 투표 알고리즘: 후보 하나와 카운터로 과반 찾기, 두 번째 패스가 필요한 이유
Boyer와 Moore가 1980년에 고안한 MJRTY는 후보 하나와 카운터 하나로 과반 원소 후보를 고릅니다. 동작 규칙, 정확성 논증, 과반이 없을 때 생기는 오답과 두 번째 패스를 원 논문 기준으로 정리합니다.
중앙값의 중앙값(BFPRT): 최악의 경우에도 선형 시간에 k번째 값 찾기
1973년 Blum·Floyd·Pratt·Rivest·Tarjan 논문의 PICK 알고리즘이 최악의 경우에도 선형 시간에 k번째 값을 찾는 원리와, 묶음 크기 5가 어디서 나오는지 원 논문 기준으로 정리합니다.
찾는 글이 없습니다. 다른 낱말로 검색해 보세요.