かなり一般的な質問があります。プログラマーとしての学校を除いて、アルゴリズムの複雑さを実際に計算する必要があったことはありますか？そして、もし..例を教えていただけませんか。
ありがとうございました ：）
1080 次
8 に答える
5
ソフトウェアを作成していて、それを実装するための複数の方法を考えることができる場合、多くの場合、（概念の複雑さと実装にかかる時間に加えて）決定要因の1つはアルゴリズムの複雑さです。したがって、上司があなたの決定を正当化することを望むとき、それぞれの複雑さを理解することが必要です。これを時期尚早の最適化の一形態と考える人もいるかもしれませんが、問題に適した設計を選択することは、優れたソフトウェアエンジニアリングであるというのがコンセンサスだと思います。
于 2009-02-03T18:40:06.963 に答える
4
絶対に-最近、アプリに問題が発生し、突然いくつかの大きな速度低下が発生し始めました。非常に主要な関数の真ん中に3次（O（n ^ 3））アルゴリズムがあることがわかりました。それは抽象化レイヤーの下に隠されていました。何が起こったのかを理解するには、関数呼び出しグラフをマッピングし、詳細を確認する必要がありました。
確かに、一度それを行った後は、O（n ^ 3）アルゴリズムに気付くために数学を適用する必要はありませんでしたが、それは主に、大学での3年間のアルゴリズム分析により、3次アルゴリズムについての一般的な感覚が得られたためです。のように見えます。
とにかく、Nは少しだけ増加したことがわかりますが、それは数百ミリ秒から数秒、そして数分に達するという先端にあります-そのため、問題はつい最近まで現れませんでした。
ほとんどの場合、複雑さを定義したパッケージ済みのアルゴリズムを使用することになります。クイックソートはO（n ^ 2）ワーストケース、O（n * log（n））平均ケース、バイナリ検索はO（log（n））などです。ライブラリは通常、パフォーマンス特性を指定します。それらがどのように構成されているかを心配する必要があります。
于 2009-02-03T18:42:31.857 に答える
3
職場では、問題を解決するためのさまざまなアルゴリズムについて何気なく話し合い、複雑さがその役割を果たします。複雑さの厳密な証明を行う必要があることは決してありませんが、一般的な「Xは実行できますが、数百万行を超える可能性があるため、O（N ^ 2）になりすぎます」。
過度の最適化は悪いコードにつながる可能性がありますが、基本的なアルゴリズムの複雑さを知ることは、プログラミングの問題を解決するための最良の方法を決定するのに大いに役立ちます。
于 2009-02-03T18:41:26.370 に答える
0
プログラミングコンテストを学校と見なすかどうかはわかりませんが、制限時間内に（指定された問題サイズの制約で）コンテストの問題を解決できるかどうかを確認するには、使用されるアルゴリズムの複雑さ。
于 2009-02-03T18:35:35.787 に答える
0
もちろん！いつでも、あなたは百万回以上何かをしている、あなたはあなたのアルゴリズムをチェックしたいかもしれません。
私が行った1つの例は、グリッドパターンに収まらなければならない何百万もの画像を生成していたときでした。申し訳ありませんが、これ以上具体的にすることはできません。
于 2009-02-03T18:41:59.270 に答える
0
はい。
一般に、複雑さはナプキンの推測には十分明白であり、パフォーマンスを測定する必要があるポイントに到達するまで、開発には問題ありません。多くの場合、私が心配していたセクションは問題なく（つまり、ナプキンの推測で十分でした）、他の何かがソフトウェアの速度を低下させています。ほとんどすべての場合、私の基本的な仮定に沿って、後でパフォーマンスを測定することにはメリットがあります。
ただし、特にグラフィックレンダリングで非常にタイムクリティカルなコードを実行している場合は、座って、アルゴリズムの複雑さと、別の方法で実行することに関連するトレードオフを決定します。
今日、私は他の誰かのコードで作業していますが、それはひどく遅いです。私は本当に気にしません-それが強化する全体的なプロセスにとって重要なすべてのために10分かかることがあります。しかし、私はバグを修正するためにコードを調べる必要がありました、そしてこの人はループ内のループ内にループを持っています、それらのほとんどは毎回異なる要素を同じ方法で同じリストを検索します。本質的に、彼は素晴らしい配列関数、たとえばfunc（i）{returnrecords[i];}を恐ろしい検索ルーチンに変更しました。
func(i)
{
for each index in records
if i==index return records[index]
next
}
現実ははるかに悪いですが、あなたはその考えを理解します。
あなたが今学校でこれを学んでいる理由は、あなたがこれらの構造を見て、それらを自動的に分類することができるようにするためです。実際にコンピューターを使用したり、複雑さを適切な数値に減らしたりする必要はないでしょうが、今手作業でそれを行わずに多くのことを確認すると、あなたもそのようなコードを作成することになり、単純に手がかりがありません。
-アダム
于 2009-02-03T18:44:27.487 に答える
0
実際に書き留めているかどうかはわかりませんが、アルゴリズムをどのように構築しているかを常に評価して、アルゴリズムの効率を改善できるかどうかを確認しています。コードについては、ネストされたループを単一のループに変換する方法、または分割統治法を使用するループから変換する方法があるかどうかを自問します。これは、O（N 2）からO（N）に、O（N）からO（log 2 N）に移動するのと同じです。SQLについても同じことが言えます-結合を削除して、インデックスを使用する代わりにサブクエリを実行できますか？おそらくO（N 2）からO（N）（または、両方のテーブル）。
于 2009-02-03T18:44:44.757 に答える
0
はいといいえ。
私は、一連のパッケージのRPM依存関係を単一のチェーンにフラット化するツールを作成していました。O(n+m)明らかな解決策の実行が遅すぎたため、グラフ理論クラスのアルゴリズムを思い出すために、記憶を少し掘り下げました。私はそれが本当にそうであったことを確認するために少し封筒裏の計算をしましたO(n+m)、そしてそれを書きそしてそれを本番環境に入れました:)
于 2009-02-03T18:45:48.497 に答える