与えられた式の平均/予想時間を見つけるには？

Question

(n * log_2 n) + (n^1.01 * (log_2 n)^10) 

これはO(n^1.03)よりも優れていますか？ 「はい」と答えることができれば、最悪の事態が判明したときの平均的なケースを得る方法を説明してください。

Answer 1

理論上、はい。 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の2倍になるためには、(n^1.03)/(n^1.01) = 2 <=> n^0.02 = 2 <=> n = 2^50が必要です。それは巨大です！