algorithm - アルゴリズム分析: 最適なアルゴリズムの選択

Question

最悪の場合の実行時間に関して2つのアルゴリズムを比較し、一方のアルゴリズムの実行時間が他方よりも速い入力サイズを見つけることに関する質問を解決しようとしています。

2 つのアルゴリズムは次のとおりです。
A ₁ = 2n log ₁₀ n
A ₂ = 0.1n ²

基本的に、n について次の不等式を解こうとしています:
2n log ₁₀ n < 0.1n ²

誰でも私を正しい方向に向けることができますか? ログ₁₀ n < 0.05n ==> n <
10 ^0.05n

しかし、ここから何をすべきかわかりません (または、解決しようとして間違った方法で行った可能性があります)。

事前に助けてくれてありがとう！

Answer 1

実際、あなたは不等式を解決しようとしています

アルゴリズムは非常に短時間だけ高速になり、n の値が大きくなるとアルゴリズムは高速になるためです。

n <= 0 の場合は無視し、10 を掛けて n で割ると、次のようになります。

次に、20 で割り、底を 10 にして両辺をべき乗します。

数値ソルバーを使用して、間隔 [1, 40] で のゼロを見つけます。40 は明らかに上限であるためです (なぜなら)。

たとえば、Matlab では次のようになります。

>> fzero(@(x) 10^(x/20)- x, 20)

ans =

   29.3531

したがって、任意の n が 29 までの整数の場合、アルゴリズムは高速になり、n > 29 の場合、アルゴリズムが優先されます。