컴퓨터 과학 알고리즘을 처음 이해합니다. 바이너리 검색의 과정을 이해하지만 효율성에 대해 약간의 오해가 있습니다.
$ s = 2 ^ n $ 요소 크기에서는 평균적으로 $ n $가 소요됩니다. 특정 요소를 찾는 단계. 양변의 밑이 2 인 로그를 취하면 $ \ log_2 (s) = n $이됩니다. 이진 검색 알고리즘의 평균 단계 수가 $ \ log_2 (s) $가되지 않습니까?
이 위키 백과 문서 이진 검색 알고리즘은 평균 성능이 $ O (\ log n) $라고 말합니다. 왜 그렇습니까?이 숫자가 $ \ log_2 (n) $가 아닌 이유는 무엇입니까?
댓글
- SO 중복- Big O (logn) 로그 기반이 e입니까?
답변
로그의 밑을 변경하면 결과 표현식은 Big-O 표기법 정의 는 두 함수가 점근 적 동작과 관련하여 동일한 클래스에 속함을 의미합니다.
예 : $$ \ log_ {10} n = \ frac {\ log_ {2} n} {\ log_ {2} 10} = C \ log_ {2} {n} $$ 여기서 $ C = \ frac {1} {\ log_ {2} 10} $.
따라서 $ \ log_ {10} n $ 및 $ \ log_ {2} n $는 상수 $ C $만큼 다르므로 둘 다 참입니다. $$ \ log_ {10} n \ text {is} O (\ log_ {2} n) $$ $$ \ log_ {2} n \ text {는} O (\ log_ {10} n) $$ 일반적으로 $ \ log_ {a} {n} $는 양의 정수 $ a $ 및 $ b $가 1보다 큰 경우 $ O (\ log_ {b} {n}) $입니다.
로그 함수의 또 다른 흥미로운 사실은 상수 $ k > 1 $의 경우 $ n ^ k $가 $ O (n) $가 아니라 $ \라는 것입니다. log {n ^ k} $는 $ O (\ log {n}) $이므로 $ \ log {n ^ k} = k \ log {n} $가 $ \ log {n} $와는 상수 계수 $ 만 다릅니다. k $.
댓글
- 양의 정수뿐만 아니라 모든 실수 $ a, b > 1 $, 예 $ e $.
- 이것이 big-O 표기법에서 로그의 밑이 일반적으로 지정되지 않는 이유라고 덧붙이고 싶습니다. 또한 $ O (\ log n) $ 기본이 사용하는 것에 대해 혼동이 없음을 의미합니다. 일반적으로 사용되는 기반이 될 수 있습니다. ' 차이를 만들지 않기 때문입니다.
Answer
fade2black의 답변 (완전히 정확함) 외에도 주목할 가치가 있습니다. “$ \ log (n) $”표기법이 모호하다는 것입니다. 기본은 실제로 지정되지 않으며 기본 기본은 컨텍스트에 따라 변경됩니다. 순수 수학에서 기본은 거의 항상 $ e $ (지정되지 않은 경우)로 가정되지만 특정 엔지니어링 컨텍스트에서는 10이 될 수 있습니다. 컴퓨터 과학에서 , base 2는 너무나 보편적이어서 $ \ log $는 종종 base 2로 간주됩니다. 위키피디아 기사는 base에 대해 아무 것도 언급하지 않습니다.
하지만 이미 보여 주었 듯이,이 경우에는 그렇지 않습니다. ” 중요하지 않습니다.
댓글
- 그때 더 주목할 가치가있는 반면 " 로그 (n) "는 " O (log (n)) "에 대해 모호 할 수 있습니다. 후자는 당신이 생각할 수있는 기초에 상관없이 단지 하나의 의미를 가지고 있기 때문이 아닙니다.