n의 제곱근은 O (log n) 또는 O (n)에 더 가깝습니까?

Question

나는 두 알고리즘 A를 가지고 알고리즘 A의 B.

시간 복잡도는 O (로그 n)을이고 B의 그 O (N)이다.

지금 나는 (수학적으로) 증명 알고리즘 A 또는 알고리즘 B가 C를

어떤 산법에 점근 가까이인지 할 필요가 O (√ N)의 시간 복잡도를 갖는 새로운 알고리즘 C가 이것에 대한 도움을 잘 부탁드립니다. 감사!

Answer 1

n의 제곱근은 O (logn) 또는 O (n)에 더 가깝습니까?

는 (나는 당신이 실제로 Θ을 의미 그 다음에 있으리라 믿고있어하지 (감사합니다. 그렇지 않으면,이 단지 상한이 있습니다) 그 지적에 대한 WhatsUp하고 당신이 말할 수 O 상한에 의해 제한 기능의 차이에 대해 아무것도.)

하자 먼저 특정 기능 로그 (n)이, √ N로 시작하고, N. 분명히, log (n) ≤ √n n (이것을 보려면 L' Hospital의 규칙을 사용할 수 있습니다). 따라서 문제는 n - √ n이 더 크거나 n - log (n)보다 작거나 같은 경우입니다. (- √ N N)/(√ N - 로그 (N)) LIM

_{N → ∞}에 L' 병원의 규칙을 적용

,

이이

것을 볼 수 있습니다

lim _{n → ∞} (1 - 0.5/,138,N)/(0.5/√ N - 1/N) = LIM _{N → ∞} (N - 0.5 √ N)/(0.5 √ N - 1) = LIM _{N → ∞} (N - 0.5 √ N)/(0.n) = ∞.

그래서 √ N는 N보다 로그 (n)이에 더 가깝다. Θ 함께

---

계산은 본질적으로 동일하지만, 더 지루한. 당신은 모든 함수가 두 개의 상수 사이에 묶여 있다고 주장 할 필요가있다. 명백하게, 그램 및 H, f를 인 경우 Θ (로그 (N)), Θ (√ N) 다음 및 Θ (N)충분히 큰 대 N 불구 (n) - f (n) < <h (n) - g (n).