34

多くの場合、答えの中には、特定の解が線形である、または別の解が二次であると言及されているものがあります。

違いを生み出す方法/何が何であるかを識別する方法は?

私のようなまだ知らない人のために、誰かがこれを最も簡単な方法で説明できますか?

4

4 に答える 4

35

これらは、Big O 記法としても知られる実行時の複雑さを参照しているに違いありません。これは取り組むべき非常に大きなトピックです。ウィキペディアの記事から始めます: https://en.wikipedia.org/wiki/Big_O_notation

このトピックを調査していたときに学んだことの 1 つは、さまざまなサイズのデータ​​ セットを使用してアルゴリズムの実行時間をグラフ化することです。結果をグラフ化すると、直線または曲線がいくつかの成長順序のいずれかに分類できることがわかります。

アルゴリズムのランタイムの複雑さを分類する方法を理解すると、アルゴリズムが時間またはメモリの観点からどのようにスケーリングするかを理解するためのフレームワークが得られます。これにより、アルゴリズムを大まかに比較して分類することができます。

私は専門家ではありませんが、これはうさぎの穴から始めるのに役立ちました。

成長の典型的な順序を次に示します。

  • O(1) - 定数時間
  • O(log n) - 対数
  • O(n) - 線形時間
  • O(n^2) - 二次
  • O(2^n) - 指数
  • O(n!) - 階乗

ウィキペディアの記事を飲み込むのが難しい場合は、iTunes University でこのテーマに関する講義を視聴し、アルゴリズム分析、big-O 記法、データ構造、さらには操作カウントのトピックを調べることを強くお勧めします。

幸運を！

于 2013-08-02T18:17:55.750 に答える
1

通常、入力サイズの観点からアルゴリズムについて議論しますn(入力が配列またはリストの場合)。n問題に対する線形の解決策は、実行時間が、 so x*n + y、ここでxとyは実数で線形にスケーリングするアルゴリズムです。n1: の最高指数で表示されますn = n^1。

二次解でnは、最高指数が 2 の項に表示されます。たとえば、x*n^2 + y*n + zです。

任意nの の場合、線形解は二次解よりも実行時間が大幅に遅くなります。

詳細については、Big O Notationを参照してください。

于 2013-08-02T18:20:40.293 に答える
1

指定しませんが、解決策について言及すると、二次収束と線形収束について質問している可能性があります。この目的のために、反復的で収束値への一連の近似値を生成するアルゴリズムがある場合、それを示すことができれば二次収束があります。

 x(n) <= c * x(n-1)^2

いくつかの正の定数c。つまり、反復時の解の誤差は、n+1反復時の誤差の 2 乗より小さいということnです。より一般的な収束率の定義に関する完全な紹介については、これを参照してくださいhttp://en.wikipedia.org/wiki/Rate_of_convergence

于 2013-08-02T18:28:50.197 に答える