복잡도 O (log (n))는 O (sqrt (n))와 동일합니까?

Question

교수님은 방금 입력의 길이를 반으로 줄이는 연산이 엄지 규칙으로 O (log (n)) 복잡성을 가졌다 고 가르쳐 주셨습니다. 그것은 왜 O (sqrt (n))가 아닌지, 둘 다 같지 않은가?

Answer 1

그들은 동등하지 않습니다 : SQRT (N) 더 로그 (N)보다 많이 증가 할 것이다. 모든 N 값에 대해 C이 없으므로 sqrt (N) < C.log (N)이 최소값보다 커야합니다.

이 잡아 쉬운 방법은, SQRT (N)은을 하겠지만 로그 ₂ (N)가 N의 (이진)의 자릿수에 가까운 값이어야한다는 것이다 숫자 자체의 반자 수가 N 인 숫자입니다. 또는, 평등 것을 명시하기 :

        로그 (N) = 2log (SQRT (N))

그래서 당신이 (대수를 취할 필요가!)가 로그 (N)과 동일한 순서로 나타 내기 위해 sqrt (N)의 값을 가져옵니다.

예를 들어, 11 자리, 0b10000000000 (= 2 ¹⁰)와 진수를 들어, 제곱근 0b100000이지만, 대수 아니, 그것은 동일하지 유일의 10

Answer 2

입니다.

@ 트렁크는 그의 대답에서 예를 들어 하나의 훌륭한 설명을주었습니다. 나는 한 점 더 더하고있다.귀하의 교수는

any operation that halves the length of the input has an O(log(n)) complexity 

그것은

any operation that reduces the length of the input by 2/3rd, has a O(log3(n)) complexity 
any operation that reduces the length of the input by 3/4th, has a O(log4(n)) complexity 
any operation that reduces the length of the input by 4/5th, has a O(log5(n)) complexity 
So on ... 

그것은 그런 다음 O(logB(n))

N:B:O(logB(n))의 복잡성을 가지고 (B-1)/Bth.하여 입력의 길이 모두 감소에도 사실, 또한 사실입니다 당신을 가르쳐 평균값은 B이고, 대수는 n

Answer 3

우리

lim {n->inf} log n/sqrt(n) = (inf/inf)

     = lim {n->inf} 1/n/1/(2*sqrt(n)) (by L'Hospital) 
         = lim {n->inf} 2*sqrt(n)/n 
         = lim {n->inf} 2/sqrt(n) 
         = 0 < inf 

가 O(.) 대안 해상력위한 https://en.wikipedia.org/wiki/Big_O_notation 참조하여 위에서 우리 log n = O(sqrt(n)) 말할 수있다 (일정한 것만으로 승산 기타) natural logarithm 가정

,

가

또한 비교 아래 함수에서 log n은 항상 n 인 경우 sqrt(n)으로 상한값입니다.

Answer 4

아니, 그들은 하지 동일; 당신도 증명할 수 (sqrt의 경우 k = 1/2) 어떤 k > 0 및 base > 1에 대한

O(n**k) > O(log(n, base)) 

. O(f(n))에 이야기 할 때

우리가 큰n, 한계에 대한 동작을 조사 할하는 좋은 수단이다. 모두 큰 O가 동일하다는 것을 가정 :

O(n**k) = O(log(n, base)) 

거기에 의미 일부

O(n**k) <= C * O(log(n, base)) 

충분히 n 일부 대형부터 일정 C하도록 유한; 다른 용어에 넣어 (log(n, base) 큰 n부터 0 아니라, 두 기능은 지속적으로 미분 가능하다) :

lim(n**k/log(n, base)) = C 
    n->+inf 

우리가 즉, L'Hospital's Rule을 사용하여 분자와 분모를 위해 파생 상품을 가지고 그들을 나눌 수 있습니다 한계 값을 확인하려면 :

lim(n**k/log(n)) = 

    lim([k*n**(k-1)]/[ln(base)/n]) = 

    ln(base) * k * lim(n**k) = +infinity 

그래서 우리는 정수를 C 등이 O(n**k) < C*log(n, base) 또는 다른 단어를이 없다는 것을 결론을 내릴 수

O(n**k) > O(log(n, base))