CLRSアルゴリズムブックから次の問題が与えられました。
次の表の各関数 f (n) と時間 t について、問題を解くアルゴリズムが f(n) マイクロ秒かかると仮定して、時間 t で解くことができる問題の最大サイズ n を決定します。
- 時間が 1 秒のとき、f(n)=nlog(n) の n をどのように計算できますか?
- f(n)=n の n をどのように計算できますか! 1秒はいつ？
質問する
1663 次
2 に答える
1
アルゴリズムには f(n) マイクロ秒かかることが記載されています。次に、そのアルゴリズムは、それぞれが 1 マイクロ秒かかる f(n) ステップで構成されると見なすことができます。
与えられた質問は、関連する f(n) 値が 1 秒に制限されていることを示しています。(つまり、10 6マイクロ秒) 次に、これらの条件を満たす最大の n を探しているので、質問は以下に示す不等式に要約されます。
1) f(n) = nlog(n) <= 10 6
2) f(n) = n! <= 10 6
残りは、主に代数と対数方程式をジャグリングして、関連する値を見つけることだと思います。
于 2016-10-07T10:37:02.787 に答える