0
(n * log_2 n) + (n^1.01 * (log_2 n)^10)
O(n^1.03)보다 낫습니까? 그렇다면 최악의 사례가 알려진 평균 사례를 얻는 방법을 설명해주십시오.주어진 표현의 평균/예상 시간을 찾는 방법?
A
답변
2
이론상 그렇습니다. O(n^p)은 p > 1 및 k > 0에 대해 O(n*log n) 및 O((log n)^k)보다 큽니다. 제 들어 n^p > (n * log n) <=> n^(p-1) > log n
:
제 들어이 부등식 n^p > (log n)^k <=> n^(p/k) > log n
모두 충분히 큰 n 위해 보류.
다른 기본 로그가 log_b(x) = log_e(x)/log_e(b)부터 상수 요소에 의해서만 다르기 때문에 로그의 기준은 부적합합니다.
반면에 최악의 경우만으로 평균 사례에 대해 말할 수있는 유일한 것은 최악의 경우보다 나쁘지 않다는 것입니다.
실제적인 언급 : n^1.03이 n^1.01의 두 배가되도록하려면 (n^1.03)/(n^1.01) = 2 <=> n^0.02 = 2 <=> n = 2^50이 필요합니다. 거대합니다!
O (n * log n)과 O ((log n)^k)를 비교하는 방법을 알려줄 수 있습니까? 나는 첫 번째와 두 번째 문장이 비교하기에 충분하다는 것을 알고 있습니까? – djay
O (n) (O (n-1)) <=> O LHS는 다항식입니다. 일반적으로'log n'은 지수에 관계없이'n'보다 작습니다. 예를 들어,'n * log n (log n) '가'n '보다 크고'n '과'(log n)^k'는'n^(1/k)'와'log n'에 해당합니다. –