Big O가 언제 로그가되는지 아는 방법은 무엇입니까?

Question

내 질문은 게시물에서 발생합니다 "큰 O에 대한 평범한 영어 설명". 로그 복잡성에 대한 정확한 의미를 모릅니다. 시간과 작업 수 사이에 회귀를 만들고 X- 제곱 값을 계산하고 복잡성을 결정할 수 있다는 것을 알고 있습니다. 그러나 종이에서 신속하게 결정하는 방법을 알고 싶습니다.

로그 복잡성을 어떻게 결정합니까? 좋은 벤치 마크가 있습니까?

Answer 1

이것이 당신이 의미하는지 확실하지 않지만 ... 로그 복잡성은 일반적으로 균형 바이너리 트리와 같은 스프레드 아웃 데이터 구조로 작업 할 때 발생합니다.이 바이너리 트리, 루트에 1 개의 노드, 2 명의 어린이, 4 명의 손자, 8이 포함되어 있습니다. 증손자 등. 기본적으로 각 레벨에서 노드 수는 일부 요소 (2)를 곱하지만 여전히 반복에 관여합니다. 또는 또 다른 예로서, 각 단계에서 인덱스가 두 배가되는 루프입니다.

for (int i = 1; i < N; i *= 2) { ... }

그런 것들은 로그 복잡성의 서명입니다.

Answer 2

엄격하지는 않지만 각 반복마다 절반으로 수행하는 데 필요한 작업을 본질적으로 나누는 알고리즘이 있습니다. 그러면 로그 복잡성이 있습니다. 전형적인 예는 이진 검색입니다.

Answer 3

마스터 정리 일반적으로 작동합니다.

Answer 4

로그 빅에 대해 알고 싶다면, 데이터가 재발의 각 단계에서 절반으로 잘라낼 때주의를 기울이십시오.

이전 단계보다 1/2 인 데이터를 처리하는 경우 무한한 시리즈이기 때문입니다.

Answer 5

여기에 또 다른 방법이 있습니다.

알고리즘이 문제의 크기의 숫자 수에서 선형이라고 가정합니다. 따라서 아마도 많은 숫자를 숫자로 표시 할 수있는 새로운 알고리즘이있을 수 있습니다. 따라서 20 자리 숫자는 알고리즘을 사용하여 10 자리 숫자보다 2 배 길이가 걸립니다. 이것은 로그 복잡성을 가질 것입니다. (그리고 발명가에게는 가치가 있습니다.)

이등분은 동일한 동작을 가지고 있습니다. 간격 길이를 1024 = 2^10으로 줄이려면 약 10 가지 이분물 단계가 필요하지만 20 단계만이 간격을 2^20으로 줄입니다.

로그 복잡성이 항상 모든 문제에 대한 알고리즘이 빠르다는 것을 의미하지는 않습니다. O (log (n)) 앞의 선형 계수가 클 수 있습니다. 따라서 알고리즘은 작은 문제에 대해 끔찍할 수 있으며, 다른 알고리즘이 지수 (또는 다항식) 사망으로 사망 할 때 문제 크기가 크게 커질 때까지 유용하지 않습니다.