큰 O 표기법으로 O (log n)을 계산하는 방법은 무엇입니까?

Question

나는 O(log n)이 문제 세트의 고정 비율 (반복적으로 O 표기법으로)에 의한 반복 감소를 가리킨다는 것을 알고있다. 그러나 얼마나 많은 반복을 실제로 얼마나 많은 수의 반복이복잡도를 가진 알고리즘이 문제가 완료되기 전에 N을 설정합니다 (하나의 요소가 남아 있음)?

Answer 1

수 없습니다. BigO를 사용하여 정확한 반복 횟수를 계산하지 마십시오.

반복 횟수에 대한 정확한 수식이있을 때 BigO를 "파생"할 수 있습니다.

숫자의 반복은 "큰"N.

더 아무것도 덜 아무것도 N 성장과 성장, 어떻게 비고 단지 정보를 제공합니다. 이를 통해 몇 가지 샘플 실행이있을 때 알고리즘이 얼마나 더 많은 작업/시간을 소비하는지 결론을 도출 할 수 있습니다. 알고리즘에 그의 과정에서 팀로 가든의 말씀으로 표현

는

Answer 2

Big O 표기법은 알고리즘이 수행 할 실제 연산 수가 아닌 크기 순서 만 보여줍니다. 루프 반복 또는 기본 연산의 정확한 수를 계산해야하는 경우 수동으로 수행해야합니다. 그러나 대부분의 실제적인 목적에서 정확한 숫자는 부적절합니다. O(log n)은 그 숫자를 알려줍니다. 연산이 증가하면 Logarythmically 올라갑니다 n

Answer 3

큰 O 표기법에서 알고리즘의 반복 횟수를 정확하게 알 수는 없습니다. 즉, 작은 수의 로그 (n)와 실제 반복 횟수의 차이는 크게 차이가 날 수 있지만 더 가깝게 가까워 질수록 덜 다른 중요도를 갖습니다.

Answer 4

:

큰 - 오 표기법는 의도 의미 높은 수준의 알고리즘 추론

에 대한 달콤한 자리를 제공하기 위해 시도 알고리즘 시간 실행과 시스템 구조, 프로그래밍 언어 또는 선택한 컴파일러에 대한 의존도를 피하는 입력 크기 간의 관계를 설명합니다.

big-Oh 표기법이 정확한 실행 시간을 제공 할 수 있다고 상상해보십시오. 즉, 오랜 시간 복잡성 함수를 알고있는 알고리즘의 경우 어떤 컴퓨터에서든지 어떻게 작동하는지 예측할 수 있습니다.

반면에, 그것은 점근 행동에 중심을두고 있습니다. 즉, 설명은 큰 n 값에 대해 더 정확합니다 (알고리즘 시간 함수의 하위 조건은 큰 오 표기법에서 무시됩니다). n 값이 낮 으면 알고리즘 성능을 향상시키려는 노력을 요구하지 않는다고 추론 할 수 있습니다.

Answer 5

몇 가지 가정을하면 일정한 요인까지 시간을 예측할 수 있습니다. 큰 가정은 크기가 무한대로 변하는 제한 동작은 관심있는 문제 크기에 대한 실제 동작과 동일하다는 것입니다.

이 가정하에, 크기 상한 시간은 NC 인 경우 인 경우 C*log(N)입니다. 상수는 로그를 계산할 때 사용하는 기준에 따라 달라집니다. 기본은 일관성이있는 한 중요하지 않습니다.하나의 크기에 대한 측정 된 시간이 있다면 C을 추정하여이를 사용하여 다른 크기의 시간을 추측 할 수 있습니다.

예를 들어, 크기 100 문제는 20 초가 걸린다 고 가정합니다. 일반 대수를 사용하면 C은 10입니다. (100의 공통 로그는 2입니다.) 1000이라는 공통 로그가 3이기 때문에 크기 1000 문제는 약 30 초가 걸릴 수 있습니다.

그러나 이것은 매우 거친 것입니다. 이 접근법은 알고리즘이 큰 문제에 유용 할 수 있는지 여부를 추정하는 데 가장 유용합니다. 그런 상황에서 메모리 크기에주의를 기울여야합니다. 일반적으로 문제를 설정하는 것은 크기면에서 선형 적이기 때문에 비용은 O(log N) 작업보다 빠르게 증가합니다.