25

私は計算複雑性のコースを受講していますが、これまでのところ、開発者にとってあまり役に立たないという印象を受けました。

私が間違っているかもしれませんが、以前にこの道をたどったことがある場合は、複雑性理論があなたの仕事にどのように役立ったかの例を教えてください。たくさんの感謝。

4

14 に答える 14

51

O（1）：ループのないプレーンコード。ただ流れる。ルックアップテーブルのルックアップもO（1）です。

O（log（n））：効率的に最適化されたアルゴリズム。例：二分木アルゴリズムと二分探索。通常は痛くありません。そのようなアルゴリズムが手元にあれば幸運です。

O（n）：データの単一ループ。非常に大きなnで痛い。

O（n * log（n））：ある種の分割統治戦略を実行するアルゴリズム。大きいnのために痛い。典型的な例：マージソート

O（n * n）：ある種のネストされたループ。nが小さくても痛い。ナイーブ行列計算で一般的です。可能であれば、この種のアルゴリズムは避けたいと思います。

O（n ^ x for x> 2）：複数のネストされたループを持つ邪悪な構造。非常に小さいnで痛い。

O（x ^ n、n！およびさらに悪い）：非常に制御された場合、非常に小さいnの場合、および本当により良い代替手段がない場合を除いて、本番コードに含めたくない奇妙な（そしてしばしば再帰的な）アルゴリズム。計算時間はn=n+1で爆発する可能性があります。

アルゴリズムをより複雑なクラスから下に移動すると、アルゴリズムが飛ぶ可能性があります。まれな場合を除いて、1960年代のハードウェアでは使用できなかったO（n * n）アルゴリズムを持つフーリエ変換について考えてみてください。次に、CooleyとTukeyは、すでに計算された値を再利用することで、複雑さを巧妙に削減しました。その結果、信号処理にFFTが広く導入されました。そして結局、スティーブ・ジョブズがiPodで大金を稼いだのもそのためです。

簡単な例：ナイーブなCプログラマーは、この種のループを記述します。

for (int cnt=0; cnt < strlen(s) ; cnt++) {
  /* some code */
}

strlen（）が実装されているため、これはO（n * n）アルゴリズムです。ループをネストすると、big-O内の複雑さが増します。O（n）内のO（n）はO（n * n）を与えます。O（n）内のO（n ^ 3）はO（n ^ 4）を与えます。この例では、文字列の長さを事前に計算すると、ループがすぐにO（n）に変わります。Joelもこれについて書いています。

しかし、複雑さのクラスがすべてではありません。nのサイズに注意する必要があります。O（n * log（n））アルゴリズムをO（n）にリワークしても、リワークによって（現在は線形の）命令の数が大幅に増えた場合は役に立ちません。そして、とにかくnが小さい場合、最適化してもあまり効果はありません。

于 2008-09-21T19:41:53.577 に答える
10

アルゴリズムの複雑さを少しでも理解していなくても、ソフトウェア開発を非常にうまく進めることができるのは事実です。複雑さに関する知識を常に使用していることに気づきました。とはいえ、この時点では気づかないことが多いです。複雑さについて学ぶことで、ソフトウェア開発者として得られる 2 つのことは、同じことを行う類似していないアルゴリズムを比較する方法です (ソート アルゴリズムは典型的な例ですが、ほとんどの人は実際には独自のソートを作成していません)。それが提供するより便利なことは、アルゴリズムをすばやく記述する方法です。

たとえば、SQL を考えてみましょう。SQL は、非常に多くのプログラマーによって毎日使用されています。次のクエリを見た場合、複雑さを研究したことがあれば、クエリの理解は大きく異なります。

SELECT User.*, COUNT(Order.*) OrderCount FROM User Join Order ON User.UserId = Order.UserId

複雑さを研究したことがあれば、誰かが特定の DBMS について O(n^2) であると言ったかどうかを理解するでしょう。複雑性理論がなければ、テーブル スキャンなどについて説明する必要があります。Order テーブルにインデックスを追加すると、

CREATE INDEX ORDER_USERID ON Order(UserId)

次に、上記のクエリは O(n log n) になる可能性があり、これは大規模な DB では大きな違いになりますが、小規模な DB ではまったく問題ありません。

データベースがどのように機能するかを理解するために複雑性理論は必要ないと主張する人もいるかもしれませんし、それらは正しいでしょうが、複雑性理論は、データに作用するアルゴリズムについて考えたり話したりするための言語を提供します。

于 2008-09-21T17:39:37.567 に答える
6

ほとんどの種類のプログラミング作業では、理論部分と証明自体は役に立たないかもしれませんが、それらが行っていることは、「このアルゴリズムは O(n^2) であるため、できる」とすぐに言える直感を与えようとすることです。これらの 100 万のデータ ポイントで実行してください。」大量のデータの最も基本的な処理でも、これに遭遇します。

ビジネス データ処理、GIS、グラフィックス プログラミング、および一般的なアルゴリズムの理解において、複雑性理論をすばやく考えることが重要でした。これは、CS の学習から得られる最も有益な教訓の 1 つです。

于 2008-09-21T17:28:50.697 に答える
4

コンピューターは賢くはなく、あなたが指示したことは何でもします。コンパイラーはコードを少し最適化できますが、アルゴリズムを最適化することはできません。人間の脳の働きは異なるため、ビッグオーを理解する必要があります。フィボナッチ数の計算を検討してください。F（n）= F（n-1）+ F（n-2）は誰もが知っていることであり、1,1から始めて、線形時間で多くの労力をかけずに次の数値を簡単に計算できます。しかし、その式を使用して（再帰的に）計算するようにコンピューターに指示すると、線形にはなりません（少なくとも、命令型言語では）。どういうわけか、私たちの脳はアルゴリズムを最適化しましたが、コンパイラはこれを行うことができません。したがって、アルゴリズムを改善するために作業する必要があります。

次に、トレーニングが必要です。非常に明白に見える脳の最適化を見つけ、コードが効果的でない場合を確認し、（計算の複雑さの観点から）悪いアルゴリズムと良いアルゴリズムのパターンを知る必要があります。基本的に、これらのコースはいくつかのことを提供します。

  • 実行パターンとデータ構造、およびそれらがプログラムの終了に必要な時間にどのような影響を与えるかを理解します。
  • 大規模なデータセットでは非効率になる可能性がある場合は、アルゴリズムの潜在的な問題を見つけるように心を鍛えます。または、プロファイリングの結果を理解します。
  • 計算の複雑さを軽減することによってアルゴリズムを改善するためのよく知られた方法を学びます。
  • クールな会社で面接に合格する準備をしてください:)
于 2008-09-21T20:15:09.517 に答える
2

はい、Big-O 記法をよく使用します。というか、記法自体ではなく、その背後にある思考プロセスを使用します。主に、組織内の開発者が非常に少ないため、私はよくそれを理解しています。私はそれらの人々に無礼になるつもりはありませんが、私の経験では、このような知識は「男性と男の子を区別する」ものの1つです.

これは、「はい」の答えしか得られない質問の 1 つなのだろうか。計算の複雑さを理解している人々の集合は、それが重要であると考えている人々の集合とほぼ同じであることに私は感銘を受けました。したがって、「いいえ」と答える可能性のある人は、おそらく質問を理解していないため、応答するために一時停止するのではなく、次の質問にスキップします. ちょっとした考え ;-）

于 2008-09-22T15:18:36.930 に答える
2

それは非常に重要です。アルゴリズムの実行にかかる時間を見積もって把握する方法を理解していないと、非常に遅いコードを書くことになります。アルゴリズムを書くときは、常に計​​算の複雑さについて考えています。これは、プログラミングをするときに常に頭に入れておくべきことです。

これは多くの場合に特に当てはまります。なぜなら、アプリは小さなテスト データ セットを使用してデスクトップ コンピューターで正常に動作するかもしれませんが、実際にアプリを使用したときにアプリがどれだけ迅速に応答するかを理解することが重要であり、何十万人もの人々がいるからです。それを使用しています。

于 2008-09-21T17:17:46.980 に答える
1

私は複雑さの計算を定期的に使用しています。これは主に、非常に大きなデータセットを使用して地理空間ドメインで作業しているためです。たとえば、数百万、場合によっては数十億のデカルト座標を含むプロセスです。多次元の問題にぶつかり始めると、1次元でO（n）になる欲張りアルゴリズムが突然3次元でO（n ^ 3）にホップし、多くのデータを必要としないため、複雑さが現実の問題になる可能性があります。深刻なボトルネックを作成します。同様の投稿で述べたように、さまざまなサイズの複雑なオブジェクトのグループを扱い始めると、大きなO表記が煩雑になることもわかります。複雑さの順序もデータに大きく依存する可能性があり、一般的なケースは、適切に設計されたアドホックアルゴリズムの一般的なケースよりもはるかに優れたパフォーマンスを発揮します。

また、プロファイラーの下でアルゴリズムをテストして、設計したものが達成したものであるかどうかを確認することも価値があります。明らかな理由から、ほとんどのボトルネックは、プロセッサ速度の向上よりもアルゴリズムの調整によってはるかにうまく解決されることがわかりました。

一般的なアルゴリズムとその複雑さの詳細については、Sedgewicksが有益でアクセスしやすいものであることがわかりました。空間アルゴリズムについては、計算幾何学に関するO'Rourkesの本が優れています。

于 2008-09-28T10:55:20.497 に答える
1

ここには多くの良いアドバイスがあり、ほとんどのプログラマーは複雑さに関する知識を時々利用したことがあると思います。

ただし、計算の複雑さを理解することは、ゲームの分野では非常に重要です。はい、聞いたことがあります。「役に立たない」ものは、​​ゲームプログラミングが生きているようなものです。

ゲーム プログラマーほど Big-O を気にかけている専門家はおそらくほとんどいないでしょう。

于 2008-09-22T15:29:01.007 に答える
1

考えなければならない問題に直面する時期があります。大量のデータセットの操作を必要とする多くの現実の問題があります...

例は次のとおりです。

  • マップ アプリケーション... Google マップなど - 世界中の道路線データをどのように処理して描画しますか? そして、あなたはそれらを素早く描く必要があります！
  • ロジスティクス アプリケーション...ステロイドを使用した巡回セールスマンを考えてみてください
  • データ マイニング... すべての大企業には 1 つ必要です。トレンドが時代遅れになる前に、100 個のテーブルと 1,000 万行以上を含むデータベースをマイニングし、有用な結果を得るにはどうすればよいでしょうか?

計算の複雑さのコースを受講すると、そのようなシナリオで効率的なアルゴリズムを分析および選択/作成するのに役立ちます。

私を信じてください、係数を減らすのと同じくらい簡単なこと、たとえば T(3n) から T(2n) に下げると、「n」が月ではなく日で測定される場合、大きな違いが生じる可能性があります。

于 2008-09-21T17:16:28.247 に答える
1

通常の生活では、コンピューターの近くではなく、複雑さと並列処理の概念を適用する必要があります。これにより、より効率的に作業を進めることができます。キャッシュの一貫性。そのようなこと。

于 2008-10-02T00:04:04.710 に答える
0

はい、並べ替えアルゴリズムに関する私の知識は、ある日、生徒の試験のスタックを並べ替えなければならなかったときに役に立ちました。マージソートを使用しました（ただし、クイックソートやヒープソートは使用していません）。プログラミングするときは、ライブラリが提供するソート ルーチンを使用するだけです。(まだ大量のデータをソートする必要はありません。)

私は常にプログラミングで複雑性理論を使用しています。主にどのデータ構造を使用するかを決定する際に使用しますが、物事をソートするかどうか、いつソートするかを決定するとき、および他の多くの決定にも使用します。

于 2008-09-21T17:28:10.170 に答える
0

良い例としては、上司から何らかのプログラムを実行するように指示されたときに、計算複雑性理論を使用して、上司が求めていることは不可能であることを証明できる場合が挙げられます。

于 2008-09-21T17:16:01.757 に答える
0

「はい」と「いいえ」

はい) 私は、アルゴリズムを開発および実装するときに、大きな O 記法を頻繁に使用します。たとえば、10^3 個のアイテムを処理する必要があり、最初のアルゴリズムの複雑さが O(n log(n)) で、2 番目のアルゴリズムが O(n^3) である場合、最初のアルゴリズムはほぼリアルタイムであり、2 番目のアルゴリズムはほぼリアルタイムであると単純に言えます。かなりの計算が必要です。

NP 複雑度クラスに関する知識が役立つ場合があります。NP完全問題を考えている問題に還元できる場合、効率的なアルゴリズムを発明することを考えるのをやめることができることに気付くのに役立ちます。

いいえ) 上で説明したことは、複雑性理論のごく一部です。結果、使っているとは言い難いですが、マイナーな部分を使っています。

アルゴリズムの開発や高度な使用方法に触れていないソフトウェア開発プロジェクトが数多くあることは認めざるを得ません。そのような場合、複雑性理論は役に立ちません。アルゴリズムの一般的なユーザーは、「速い」と「遅い」、「x 秒」などの言葉を頻繁に使用して操作します。

于 2008-09-21T17:41:40.713 に答える
0

@Martin: その背後にある思考プロセスについて詳しく教えてください。

座って解決策の Big-O 表記法を考え出すほど明確ではないかもしれませんが、問題に対する認識が生まれます。それにより、より効率的な答えを探すようになり、アプローチの問題から遠ざかることができます。 . 例: O(n*n) 対より高速な例: リストに格納された単語とトライに格納された単語の検索 (不自然な例)

どのデータ構造を使用するか、および大量のレコードをどのように処理するかによって、違いが生じることがわかりました。

于 2008-09-22T17:23:01.967 に答える