[algorithm] 알고리즘이 O (log log n) 복잡성을 갖게하는 원인은 무엇입니까?

Program / 글쓴이

이 이전 질문 은 알고리즘이 O (log n) 복잡성을 갖도록 만들 수있는 몇 가지 요인을 다룹니다.

알고리즘이 시간 복잡성 O (log log n)를 갖게하는 원인은 무엇입니까?

답변

O (log log n) 용어는 다양한 위치에 나타날 수 있지만 일반적으로이 런타임에 도착하는 두 가지 주요 경로가 있습니다.

제곱근으로 축소

연결된 질문에 대한 답변에서 언급했듯이 알고리즘이 시간 복잡도 O (log n)를 갖는 일반적인 방법은 해당 알고리즘이 각 반복에서 일정한 요소만큼 입력의 크기를 반복적으로 줄여서 작동하는 것입니다. 이 경우 알고리즘은 O (log n) 반복 후에 종료해야합니다. 상수로 O (log n) 나누기를 수행 한 후 알고리즘은 문제 크기를 0 또는 1로 축소해야하기 때문입니다. , 이진 검색의 복잡성은 O (log n)입니다.

흥미롭게도 O (log log n) 형식의 런타임을 생성하는 문제의 크기를 줄이는 유사한 방법이 있습니다. 각 레이어에서 입력을 반으로 나누는 대신 각 레이어 에서 크기의 제곱근을 취하면 어떻게 될까요?

예를 들어 65,536이라는 숫자를 봅시다. 1이 될 때까지 몇 번이나 2로 나누어야합니까? 이렇게하면

  • 65,536 / 2 = 32,768
  • 32,768 / 2 = 16,384
  • 16,384 / 2 = 8,192
  • 8,192 / 2 = 4,096
  • 4,096 / 2 = 2,048
  • 2,048 / 2 = 1,024
  • 1,024 / 2 = 512
  • 512/2 = 256
  • 256/2 = 128
  • 128/2 = 64
  • 64/2 = 32
  • 32/2 = 16
  • 16/2 = 8
  • 8/2 = 4
  • 4/2 = 2
  • 2/2 = 1

이 프로세스는 16 단계를 거치며 65,536 = 2 16 인 경우이기도합니다 .

그러나 각 수준에서 제곱근을 취하면

  • √65,536 = 256
  • √256 = 16
  • √16 = 4
  • √4 = 2

2까지 내려가는 데 4 단계 만 필요합니다. 왜 그런가요?

첫째, 직관적 인 설명입니다. 숫자 n과 √n에는 몇 자리가 있습니까? 숫자 n에는 대략 log n 자리가 있고 √n에는 대략 log (√n) = log (n 1/2 ) = (1/2) log n 자리가 있습니다. 즉, 제곱근을 취할 때마다 숫자의 자릿수를 대략 절반으로 줄입니다. 수량이 상수 (예 : 2)로 떨어지기 전에 k O (log k) 번만 절반으로 줄일 수 있기 때문에, 이는 숫자를 줄이기 전에 제곱근 O (log log n) 번만 취할 수 있음을 의미합니다. 일부 상수 (예 : 2)로.

이제이를 엄격하게 만들기 위해 몇 가지 수학을 해봅시다. 위의 순서를 2의 거듭 제곱으로 다시 작성합니다.

  • √65,536 = √2 16 = (2 16 ) 1/2 = 2 8 = 256
  • √256 = √2 8 = (2 8 ) 1/2 = 2 4 = 16
  • √16 = √2 4 = (2 4 ) 1/2 = 2 2 = 4
  • √4 = √2 2 = (2 2 ) 1/2 = 2 1 = 2

시퀀스 2 16 → 2 8 → 2 4 → 2 2 → 2 1 을 따랐습니다 . 반복 할 때마다 2의 거듭 제곱 지수를 반으로 자릅니다. 이것은 우리가 이미 알고있는 것과 다시 연결되기 때문에 흥미 롭습니다. 0으로 떨어지기 전에 숫자 k를 O (log k)의 절반으로 나눌 수 있습니다.

따라서 임의의 수 n을 가져 와서 n = 2 k 로 씁니다 . n의 제곱근을 취할 때마다이 방정식의 지수를 반으로 줄입니다. 따라서 k가 1 이하로 떨어지기 전에 적용되는 O (log k) 제곱근 만있을 수 있습니다 (이 경우 n이 2 이하로 떨어짐). n = 2 k 이므로 k = log 2 n이므로 취한 제곱근의 수는 O (log k) = O (log log n)입니다. 따라서 문제를 원래 문제 크기의 제곱근 크기의 하위 문제로 반복해서 축소하여 작동하는 알고리즘이있는 경우 해당 알고리즘은 O (log log n) 단계 후에 종료됩니다.

이에 대한 실제 사례 중 하나는 van Emde Boas 트리입니다.(vEB-tree) 데이터 구조. vEB- 트리는 0 … N-1 범위의 정수를 저장하기위한 특수 데이터 구조입니다. 다음과 같이 작동합니다. 트리의 루트 노드에는 0 … N-범위를 분할하는 √N 포인터가 있습니다. 1을 √N 버킷에 각각 대략 √N 정수 범위를 포함합니다. 그런 다음 이러한 버킷은 각각 내부적으로 √ (√ N) 버킷으로 세분되며, 각 버킷은 대략 √ (√ N) 요소를 보유합니다. 트리를 탐색하려면 루트에서 시작하여 자신이 속한 버킷을 결정한 다음 적절한 하위 트리에서 반복적으로 계속합니다. vEB- 트리가 구조화되는 방식으로 인해 어떤 하위 트리로 내려 갈지 O (1) 시간에 결정할 수 있으므로 O (log log N) 단계 후에는 트리의 맨 아래에 도달하게됩니다. 따라서 vEB 트리에서 조회하는 데 시간이 걸리는 것은 O (log log N)뿐입니다.

또 다른 예는 Hopcroft-Fortune 가장 가까운 포인트 쌍 알고리즘 입니다. 이 알고리즘은 2D 점 집합에서 가장 가까운 두 점을 찾으려고합니다. 버킷 그리드를 만들고 해당 버킷에 포인트를 분배하는 방식으로 작동합니다. 알고리즘의 어느 지점에서나 √N 개 이상의 포인트가있는 버킷이 발견되면 알고리즘은 해당 버킷을 재귀 적으로 처리합니다. 따라서 재귀의 최대 깊이는 O (log log n)이고 재귀 트리의 분석을 사용하여 트리의 각 계층이 O (n) 작업을 수행함을 보여줄 수 있습니다. 따라서 알고리즘의 총 실행 시간은 O (n log log n)입니다.

작은 입력에 대한 O (log n) 알고리즘

크기가 O (log n) 인 개체에 대한 이진 검색과 같은 알고리즘을 사용하여 O (log log n) 런타임을 달성하는 다른 알고리즘이 있습니다. 예를 들어, x-fast trie 데이터 구조는 높이 O (log U)의 트리 계층에 대해 이진 검색을 수행하므로 일부 작업의 런타임은 O (log log U)입니다. 관련된 y-fast trie 는 O (log U) 노드의 균형 잡힌 BST를 각각 유지하여 O (log log U) 런타임 중 일부를 가져와 해당 트리에서 검색이 O (log log U) 시간에 실행되도록합니다. 탱고 트리 및 관련 multisplay 나무 가 O (로그 n)이 항목을 각각 포함하고 나무를 유지하기 때문에 데이터 구조는 분석에 O (로그 로그 n)의 용어와 끝까지.

다른 예

다른 알고리즘은 다른 방식으로 런타임 O (log log n)를 달성합니다. 보간 검색 은 정렬 된 배열에서 숫자를 찾기 위해 런타임 O (log log n)를 예상했지만 분석이 상당히 관련되어 있습니다. 궁극적으로 분석은 반복 횟수가 n 2 -k ≤ 2이고 log n이 올바른 해가되는 수 k와 동일하다는 것을 보여줌으로써 작동 합니다. Cheriton-Tarjan MST 알고리즘 과 같은 일부 알고리즘 은 복잡한 제약 최적화 문제를 해결하여 O (log log n)를 포함하는 런타임에 도달합니다.

도움이 되었기를 바랍니다!

답변

시간 복잡도에서 O (log log n)의 요소를 보는 한 가지 방법은 다른 답변에서 설명한 것과 같이 나누는 것입니다. 그러나 시간과 공간 / 시간 사이의 거래를 원할 때이 요소를 보는 또 다른 방법이 있습니다. 알고리즘의 근사치 / 시간 및 경도 / … 알고리즘에 인공적인 반복이 있습니다.

예를 들어 SSSP (단일 소스 최단 경로)는 평면 그래프에서 O (n) 알고리즘을 가지고 있지만 복잡한 알고리즘 이전에는 실행 시간이 O (n log log n) 인 훨씬 더 쉬운 알고리즘 (그러나 여전히 다소 어렵습니다)이있었습니다. 알고리즘의 기본은 다음과 같습니다 (매우 대략적인 설명 이며이 부분을 이해하지 않고 답변의 다른 부분을 읽을 것을 제안합니다).

  1. 몇 가지 제한을두고 그래프를 크기 O (log n / (log log n))의 부분으로 나눕니다.
  2. 언급 된 각 부분이 새 그래프 G ‘의 노드라고 가정하고 시간 O (| G’| * log | G ‘|) ==> 여기서 G’에 대한 SSSP를 계산합니다. = O (| G | * log log n / log n) 우리는 (log log n) 인자를 볼 수 있습니다.
  3. 각 부분에 대해 SSSP를 계산합니다. 다시 한 번 O (| G ‘|) 부분이 있고 시간 내에 모든 부분에 대해 SSSP를 계산할 수 있기 때문입니다. | n / logn | * | log n / log logn * log (logn / log log n).
  4. 업데이트 가중치,이 부분은 O (n)에서 수행 할 수 있습니다. 자세한 내용은 이 강의 노트 가 좋습니다.

그러나 내 요점은 여기서 우리는 크기가 O (log n / (log log n))가되도록 나누기를 선택합니다. O (log n / (log log n) ^ 2)와 같은 다른 나눗셈을 선택하면 더 빨리 실행되고 다른 결과를 가져올 수 있습니다. 많은 경우 (근사 알고리즘이나 무작위 알고리즘 또는 위와 같은 SSSP와 같은 알고리즘에서) 무언가를 반복 할 때 (하위 문제, 가능한 솔루션 등), 우리는 그 거래에 해당하는 반복 횟수를 선택합니다. 우리는 (시간 / 공간 / 알고리즘의 복잡성 / 알고리즘의 상수 인자, …)를 가지고 있습니다. 따라서 실제 작동하는 알고리즘에서 “log log n”보다 더 복잡한 것을 볼 수 있습니다.

답변