0

同じ問題を解決する2つのアルゴリズムの実行時関数を指定しました。まあ言ってみれば -

最初のアルゴリズムの場合: T(n) = an + b(nの線形）
2番目のアルゴリズムの場合:( T(n) = xn^2 + yn + znの2次）

すべての本は、時間の線形は二次よりも優れていると言っています、そしてもちろんそれはより大きなものnです（どれくらい大きいですか？）。a定数、、、、にb基づいた大きな変化の定義をx感じyますz。

nalgo2からalgo1に、またはその逆に切り替える必要がある場合のしきい値を見つける方法を教えてください（実験によってのみ見つかりますか？）。誰かがプロのソフトウェア開発組織でどのように行われているのか説明していただければ幸いです。

私の質問を説明できるといいのですが、そうでない場合はお知らせください。

よろしくお願いします。

PS-実装はJavaで行われ、さまざまなプラットフォームで実行されることが期待されます。a定数、、、bを数学的にx推定するのは非常に難しいと思います。プロのソフトウェア開発におけるこのジレンマをどのように解決しますか？yz

4

6 に答える 6

5

私はいつもO（n）を使用します。nが小さいほど遅くなる可能性がありますが、とにかくnは小さいです。コードが複雑になると、各データセットに最適なアルゴリズムを選択しようとすると、デバッグと保守が難しくなります。

于 2012-07-13T08:26:00.873 に答える
2

実際に関心のあるすべての場合において、固定係数を推定することは不可能です。できたとしても、入力のサイズが将来どのように変化するかを予測できなければ、役に立ちません。

他の要因（メモリ消費など）も関係しない限り、線形アルゴリズムを常に優先する必要があります。実用的なパフォーマンスが許容できない場合は、代替案を探すことができます。

于 2012-07-13T08:26:39.840 に答える
1

予想される入力サイズでコードをプロファイリングするだけです。最悪の場合の入力も追加するとさらに良いでしょう。方程式を解くのに時間を無駄にしないでください。そもそもそれを導き出すことは不可能かもしれません。

一般に、n = 10000のサイズからO（n 2）はO（n）よりも大幅に遅いと予想できます。大幅に遅いということは、人間が遅いことに気付くことができることを意味します。アルゴリズムの複雑さによっては、nが小さいほど違いに気付く場合があります。

重要なのは、時間計算量に基づいてアルゴリズムを判断することで、最大の入力サイズの入力に対して明らかに遅すぎるアルゴリズムを無視できるようになるということです。ただし、入力データのドメインによっては、複雑度の高い特定のアルゴリズムは、時間計算量の低い他のアルゴリズムよりも実質的にパフォーマンスが高くなります。

于 2012-07-13T08:24:27.787 に答える
1

あなたはプログラミングの質問ではなく、数学の質問をしているのです。

NB私はxが正であると仮定するつもりです...

あなたはいつ知る必要があります

an+b < xn^2 + yn + z

すなわち

0 < xn^2 + (y-a)n + (z-b)

これを二次方程式を解くための標準方程式にプラグインできますhttp://en.wikipedia.org/wiki/Quadratic_equation#Quadratic_formula

そして、大きい方の0をとると、これより大きいすべての値（xが正の場合）でO（n ^ 2）が大きくなることがわかります。

あなたはx、y、a、z、bを含む恐ろしい方程式になってしまいます。

于 2012-07-13T08:32:54.940 に答える
1

実験。また、インスタンスのリストから特定のインスタンスを見つけるためのコードがある状況に遭遇しました。元のコードは単純なループを実行しましたが、これは数年間うまく機能しました。かつて、お客様の1人がパフォーマンスの問題を記録しました。彼の場合、リストには数千のインスタンスが含まれており、ルックアップは非常に低速でした。

私の仲間の開発者の解決策は、リストにハッシュを追加することでした。これにより、実際に顧客の問題が解決されました。しかし、突然パフォーマンスの問題が発生したため、他の顧客から不満が出始めました。ほとんどの場合、リストには少数（約10）のエントリしか含まれておらず、ハッシュはリストをループするよりもはるかに低速でした。

最終的な解決策は、両方の選択肢（ループとハッシュ）の時間を測定し、ループがハッシュよりも遅くなるポイントを特定することでした。私たちの場合、これは約70でした。そこで、アルゴリズムを変更しました。

  • リストに含まれるアイテムが70未満の場合、ループします
  • リストに70を超えるアイテムが含まれている場合は、ハッシュします

あなたの場合、解決策はおそらく似ているでしょう。

于 2012-07-17T06:48:51.977 に答える
0

大規模な目的でアルゴリズムを作成する場合、大きな「n」に対して適切に実行する必要があります。あなたの場合、に応じてa, b, x, y and z、2番目のアルゴリズムは2次式であるにもかかわらずパフォーマンスが向上する可能性があります。ただし、の値が何であっても、 （たとえば）a, b, x, y and zの下限があり、それを超えると、最初のアルゴリズム（線形のアルゴリズム）が常に2番目のアルゴリズムよりも高速になります。nn0

If f(n) = O(g(n))
then it means for some value of n >= n0 (constant)
f(n) <= c1*g(n)

So
if g(n) = n,
then f(n) = O(n)

だからあなたの使用法に応じてアルゴを選択してくださいn

于 2012-07-17T06:42:01.293 に答える