max{k,n/k}
k=n
- 이산 로그를 계산하기위한 베이비 스텝 자이언트 스텝 알고리즘 ,
O(n) - 시간 및 메모리에서의 정적 2D 직교 범위 계산 ,O(n)
O(n) O(n) - EXTRACT-MIN이 있고 에 DECREASE-KEY가있는 우선 순위 큐 ,O(1)
O(nk) O(1) - 다항식 시간에 색상 으로 3 색 그래프를 채색 ,
O(n)
몇가지 말하자면.
그러한 알고리즘은 종종 차선책이지만, 학생들은 이해하기 쉽고 순진한 경계가 최적이 아님을 신속하게 보여줄 수 있습니다. 또한, 제곱근 아이디어 데이터 구조는 캐시 친 화성 (캐시 불명확 한 기술을 고려하지 않음)으로 인해 이진 트리 기반 대응보다 더 실용적입니다. 그렇기 때문에 제가 가르치는 동안이 주제에 대해 약간의주의를 기울입니다.
나는 이런 종류의 더 독특한 예에 관심이 있습니다. 그래서 나는 분석이 제곱근 아이디어에 의존하는 (바람직하게는 우아한) 알고리즘, 데이터 구조, 통신 프로토콜 등을 찾고 있습니다. 그들의 증상이 최적 일 필요는 없습니다.
답변
Chazelle, Liu 및 Magen의 논문 Sublinear Geometric Algorithms (STOC 2003, SICOMP 2006)에는 다음과 같은 임의 샘플링 트릭을 영리하게 적용했습니다. 동일한 트릭의 변형은 이전 에 CLR (1990)의 첫 번째 버전을 인용 한 Gärtner와 Welzl [ DCG 2001 ]에 의해 사용되었습니다 .
인접한 메모리 블록에 저장된 정렬 된 원형 링크 된 숫자 목록이 있다고 가정하십시오. 즉, 우리는 두 개의 배열이 있습니다 및 N e x t [ 1 .. n ]가 있습니다 . 여기서
Key[1..n]Next[1..n]
- 은 임의의 순서로 n 개의 숫자집합을 저장합니다.
Key[1..n] n - 경우 설정된 최대 수는 다음 K의 전자 Y [ N E X t [ I ] ] 세트에서 가장 작은 수이고; 그렇지 않으면, K e y
Key[i] Key[Next[i]] 는 K e y [ i ] 보다 큰 세트에서 가장 작은 수입니다. Key[Next[i]] Key[i]
그런 다음 주어진 숫자 의 후계자를 O 에서 찾을 수 있습니다 ( √
x예상 시간은 다음과 같습니다.
O(n)-
√ 의 랜덤 샘플을 선택하십시오 배열의 요소K의전자Y
nKey
. 하자 보다 작은 최대 샘플 수 (X) (모든 샘플보다 큰 경우, 또는 큰 샘플 X ).
Key[j]x
x
-
N e x t를 따르십시오
Next의 포인터 우리는보다 큰 번호가 표시 혹은 등전위까지 X (모든 샘플보다 크게된다면 감싸 후 X ).
Key[j]x
x
야오의 명예를 비교적 간단하게 적용하면
O(n)Ω(n)