[math] Big O (logn) log base e입니까?

이진 검색 트리 유형의 데이터 구조의 경우 Big O 표기법은 일반적으로 O (logn)로 표시됩니다. 로그에 소문자 ‘l’이있는 경우 자연 로그로 설명되는 로그 밑 e (n)를 의미합니까? 간단한 질문에 대해 죄송하지만 다른 묵시적 로그를 구분하는 데 항상 어려움이있었습니다.

답변

big-O () 표기법으로 표현되면 둘 다 맞습니다. 그러나 O () 다항식을 유도 하는 동안 이진 검색 의 경우 로그 ₂ 만 정확합니다. 나는이 구별이 귀하의 질문이 시작되는 직관적 인 영감이라고 가정합니다.

또한 내 의견으로는 O (log ₂ N)를 하는 것이 알고리즘의 런타임 파생을 더 잘 전달하기 때문에 예제에 더 좋습니다.

big-O () 표기법에서는 상수 인자가 제거됩니다. 한 로그 밑에서 다른 로그 밑으로 변환하려면 상수 인자를 곱해야합니다.

따라서 O (log N)는 상수 인자로 인해 O (log ₂ N) 와 같습니다 .

그러나 대답에 log ₂ N을 쉽게 입력 할 수 있다면 그렇게하는 것이 더 교육적입니다. 이진 트리 검색 의 경우 big-O () 런타임을 유도하는 동안 log ₂ N이 도입되는 것이 맞습니다 .

결과를 big-O () 표기법으로 표현하기 전에 차이가 매우 중요합니다. big-O 표기법을 통해 전달되는 다항식을 유도 할 때이 예제 에서는 O () 표기법을 적용하기 전에 log ₂ N 이외의 로그를 사용하는 것은 올바르지 않습니다 . 다항식이 big-O () 표기법을 통해 최악의 런타임을 전달하는 데 사용되는 즉시 어떤 로그가 사용되는지는 중요하지 않습니다.

답변

상이한 기지의 모든 대수가 있기 때문에 큰 O 표기법은 대수베이스의 영향을받지 않는 일정한 인자에 의해 관련 , O(ln n)동일하다 O(log n).

답변

big-O 표기법은 일반적으로 점근 적으로 가장 높은 차수 만 표시하므로 기본이 무엇인지는 중요하지 않으므로 n상수 계수가 사라집니다. 다른 로그 밑은 상수 계수와 동일하므로 불필요합니다.

즉, 아마도 log base 2를 가정 할 것입니다.

답변

둘 다 맞습니다. 이것에 대해 생각하다

log2(n)=log(n)/log(2)=O(log(n))
log10(n)=log(n)/log(10)=O(log(n))
logE(n)=log(n)/log(E)=O(log(n))

답변

예, big-O 표기법에 대해 이야기 할 때 기본은 중요하지 않습니다. 그러나 실제 검색 문제에 직면했을 때 계산적으로 중요합니다.

트리 구조에 대한 직관을 개발할 때 이진 검색 트리는 트리의 높이 인 O (n log n) 시간에 검색 할 수 있다는 것을 이해하면 도움이됩니다. 즉, n 노드가있는 이진 트리에서 트리 깊이는 O (n log n) (밑수 2)입니다. 각 노드에 3 개의 자식이있는 경우 트리는 O (n log n) 시간 내에 검색 할 수 있지만 밑이 3 인 로그를 사용합니다. 계산적으로 각 노드의 자식 수는 성능에 큰 영향을 미칠 수 있습니다 (예 : 링크 텍스트 참조). ).

즐겨!

폴

답변

기술적으로 기본은 중요하지 않지만 일반적으로 기본 2로 생각할 수 있습니다.

답변

먼저 함수 f (n)이 O (g (n))라는 의미를 이해해야합니다.

공식적인 정의는 다음과 같습니다. * A 함수 f (n)은 O (g (n)) iff | f (n) | <= C * | g (n) | n> k 일 때마다, 여기서 C와 k는 상수입니다. *

따라서 f (n) = log base a of n, 여기서 a> 1 및 g (n) = log base b of n, 여기서 b> 1

노트: 이는 a 및 b 값이 1보다 큰 값일 수 있음을 의미합니다 (예 : a = 100 및 b = 3).

이제 우리는 다음을 얻습니다. n의 log base a는 O (log base b of n)라고합니다. | log base a of n | <= C * | n의 밑수 b | n> k 일 때마다

k = 0, C = log base a of b를 선택합니다.

이제 방정식은 다음과 같습니다. | log base a of n | <= log base a of b * | log base b of n | n> 0 일 때

이제 방정식은 다음과 같습니다. | log base a of n | <= | n의 밑수 a | n> 0 일 때

방정식은 제한 a, b> 1 및 n> 0을 제외하고 값 n, b 또는 a가 무엇이든 항상 참입니다. 따라서 n의 log base a는 O (log base b of n)이며 a, b는 중요하지 않으므로 간단히 생략 할 수 있습니다.

여기에서 YouTube 비디오를 볼 수 있습니다 : https://www.youtube.com/watch?v=MY-VCrQCaVw

여기에서 기사를 읽을 수 있습니다 : https://medium.com/@randerson112358/omitting-bases-in-logs-in-big-o-a619a46740ca