태그 보관물: big-list

big-list

복잡성 분석에서 제곱근 아이디어의 주목할만한 예 학생들은 이해하기 쉽고

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

    n

    Key

    . 하자 보다 작은 최대 샘플 수 (X) (모든 샘플보다 큰 경우, 또는 큰 샘플 X ).

    Key[j]

    x

    x

  • N e x t를 따르십시오

    Next

    의 포인터 우리는보다 큰 번호가 표시 혹은 등전위까지 X (모든 샘플보다 크게된다면 감싸 후 X ).

    Key[j]

    x

    x

야오의 명예를 비교적 간단하게 적용하면

O(n)

Ω(n)


답변

O(m3/2)

m

O(m3/2)

nk

k

nk

k

m/k+k

O(m)

O(m3/2)


답변