最近のインタビューで、技術的な質問の過程で出てきたさまざまなアルゴリズムの Big-O に関連するいくつかの質問をされました。私はこれについてあまりうまくやれなかったと思います...アルゴリズムのBig-Oを計算するように求められたプログラミングコースを受講してから10年間、私は何かの「Big-O」について一度も議論したことがありません手がけたり、デザインしたりしました。私は、コードの複雑さと速度について、他のチーム メンバーや一緒に働いたアーキテクトと多くの議論に参加してきましたが、実際のプロジェクトで Big-O 計算を実際に使用したチームの一員になったことはありません。議論は常に「アウトデータを理解した上で、これを行うためのより良い、またはより効率的な方法はありますか?」というものです。「このアルゴリズムの複雑さは何ですか」ということはありませんか?
人々が実際にコードの「Big-O」について実際に議論しているのかどうか疑問に思っていましたか?
それを使用することはあまりなく、その意味を理解することが重要です。
O(N^2) ソート アルゴリズムを使用した結果を認識していないプログラマーがいます。
学界で働いている人以外の多くの人が、Big-O Complexity Analysis を日常的に怒って使用するとは思えません。
不要な n 2 乗はありません
私の経験では、議論する必要がないため、それについて多くの議論はありません。実際には、私の経験では、実際には O(n log n) または O(n) である可能性があるときに、何かが遅いことを発見し、それが O(n^2) であることを確認するだけです。それを変更。「それは n-squared です。直してください」以外の議論はありません。
はい、私の経験では、あなたはそれをかなり一般的に使用していますが、「多項式の次数を減らす」という最も基本的な意味でのみ使用され、「はい、しかしこのクレイジーなアルゴリズムに切り替えると、 logN からアッカーマン関数の逆関数まで増加する」またはそのようなナンセンス. 多項式よりも小さいものはすべて、理論が窓の外に出て、プロファイリングに切り替えます (たとえば、O(n) と O(n log n) の間で決定する場合でも、実際のデータを測定します)。
Big-O 表記法はどちらかというと理論的なものですが、実際には、実際のプロファイリング結果に関心があり、パフォーマンスがどのようになっているのかを正確に知ることができます。
O(n^2)本によるとO(nlogn)上限がある2つのソートアルゴリズムがあるかもしれませんが、プロファイリングの結果は、より効率的な方がいくらかのオーバーヘッドがある可能性があることを示すかもしれません(これは、あなたが見つけた理論上の限界には反映されていません)。を扱っている場合は、理論的に効率の低いソート アルゴリズムを選択することもできます。
結論: 実生活では、プロファイリングの結果は通常、理論的なランタイムの境界よりも優先されます。
私はいつもそうします。私の場合は通常、ユーザー、データベース内の行、プロモーションコードなど、「大きな」数を処理する必要がある場合は、アルゴリズムの Big-O を知って考慮する必要があります。
たとえば、配布用のランダムなプロモーション コードを生成するアルゴリズムを使用して、数十億のコードを生成することができます... O(N^2) アルゴリズムを使用して一意のコードを生成すると、数週間の CPU 時間を意味しますが、O(N) は数時間を意味します.
もう 1 つの典型的な例は、コード内のクエリです (まずい!)。人々はテーブルを検索し、各行に対してクエリを実行します...これにより、順序がN ^ 2になります。通常、コードを変更して SQL を適切に使用し、N または NlogN の順序を取得できます。
したがって、私の経験では、プロファイリングは正しいクラスのアルゴリズムが使用された後にのみ役立ちます。私はプロファイリングを使用して、「小さい」数のバインドされたアプリケーションのパフォーマンスが低下する理由を理解するなど、悪い動作を検出します。
私の個人的な経験からの答えは、いいえです。おそらくその理由は、単純でよく理解されたアルゴリズムとデータ構造のみを使用しているからです。彼らの複雑さの分析は、数十年前にすでに行われ、公開されています。手の込んだアルゴリズムを避けるべき理由については、Rob Pike がより適切に説明しています。つまり、実践者が新しいアルゴリズムを発明する必要はほとんどなく、その結果、Big-O を使用する必要もほとんどありません。
だからといって、Big-O に習熟してはいけないというわけではありません。プロジェクトでは、まったく新しいアルゴリズムの設計と分析が必要になる場合があります。実際の例については、Skiena のThe Algorithm Design Manualの「戦争の話」を参照してください。
for3 つの入れ子になったループは、1 つの入れ子になったループよりもおそらく悪いことを知っている範囲でfor。というか、勘の参考にしています。
学界以外でアルゴリズムの Big-O を計算したことはありません。特定の問題にアプローチする方法が 2 つある場合、直感的に一方の Big-O が他方よりも低いと判断された場合、それ以上分析せずに、おそらく本能的に小さい方を選択します。
一方、アルゴリズムに取り込まれるnのサイズが確実にわかっていて、それが比較的小さい (たとえば、100 要素未満) ことが確実にわかっている場合は、最も読みやすいものを使用する可能性があります (知りたい私のコードが書かれてから 1 か月後でも何をするか)。結局のところ、100^2 と 100^3 の実行の違いは、今日のコンピューターを使用しているユーザーにはほとんどわかりません (そうでないことが証明されるまで)。
しかし、他の人が指摘しているように、プロファイラーには最後の明確な言葉があります。私が書いたコードの実行が遅い場合、理論上のルールよりもプロファイラーを信頼し、それに応じて修正します。
はい、使っています。いいえ、「orderCount」または「xyz」のどちらがより適切な変数名であるかについてあまり議論しないのと同じように、「議論」されることはあまりありません。
通常、座って分析することはありませんが、知っていることに基づいて直感を開発しO、ほとんどの場合、複雑さをその場でほぼ見積もることができます。
私は通常、多くのリスト操作を実行する必要があるときに少し考えます。線形時間で実行できたはずの、不必要にO(n^2)複雑なことを行っていますか? リストを何回パスしましたか? 正式な分析を行う必要はありませんが、big-O 表記法に関する知識がなければ、正確に分析することは非常に難しくなります。
ソフトウェアがより大きな入力サイズで許容できるパフォーマンスを発揮するようにしたい場合は、公式または非公式に、アルゴリズムの非常に複雑なことを考慮する必要があります。プロファイリングは、プログラムが現在どのように実行されているかを伝えるのに最適ですが、アルゴリズムを使用している場合O(2^n) 、プロファイラーは、入力サイズが小さい限りすべてが問題ないと伝えます. そして、入力サイズが大きくなり、ランタイムが爆発します。
big-O 表記を「理論的」、「役に立たない」、または「プロファイリングほど重要ではない」として却下することがよくあります。これは、ビッグオーの複雑さが何のためにあるのかを理解していないことを示しています。プロファイラーとは異なる問題を解決します。どちらも、優れたパフォーマンスのソフトウェアを作成する上で不可欠です。しかし、プロファイリングは最終的に事後対応型のツールです。問題が存在すると、問題がどこにあるかがわかります。
Big-O の複雑さは、より大きな入力で実行した場合にコードのどの部分が爆発するかを事前に通知します。プロファイラーはそれを教えてくれません。
いいえ、「実世界」の状況では Big-O の複雑さを使用しません。
問題全体に対する私の見解は次のとおりです-（おそらく間違っている..しかし、それは私の見解です。）
Big-O の複雑さは、究極的には、アルゴリズムがどれほど効率的であるかを理解することです。経験またはその他の手段から、扱っているアルゴリズムを理解し、適切な場所で適切なアルゴリズムを使用できる場合、それがすべて重要です。
このBig-Oのことを知っていて、それを適切に、うまく、うまく使うことができれば.
アルゴとその効率について数学的な方法で話すことを知らなくても (Big-O のようなもの)、本当に重要なこと (状況で使用するのに最適なアルゴ) を知っている場合は、まったく問題ありません。
どちらもわからない場合は、悪いです。
コードの一部を詳細に分析する必要はめったにありませんが、それが何を意味するのかを理解し、作成しているコードの複雑さとその結果をすばやく評価できることが重要です。
開発時には、「十分」だと感じることがよくあります。ええと、誰もこの配列に100を超える要素を入れることはありませんよね？次に、ある日、誰かが配列に1000個の要素を配置します（ユーザーを信頼します。コードで許可されている場合は、そのうちの1人がそれを実行します）。そして、今では十分に優れていたそのn ^ 2アルゴリズムは、大きなパフォーマンスの問題です。
逆の場合もあります。機能的にn^2の操作を行う必要があり、アルゴリズムの複雑さがn ^ 3であることがわかっている場合は、n^2にするために何かできることがあるかもしれません。n ^ 2になったら、より小さな最適化に取り組む必要があります。
逆に、ソートアルゴリズムを作成したばかりで、それが線形の複雑さを持っていることがわかった場合は、問題があることを確認できます。（もちろん、実際には、独自のソートアルゴリズムを作成しなければならないことはまれですが、インタビューで、彼の1つのforループソートアルゴリズムに明らかに満足している人を見たことがあります）。
はい、サーバー側のコードの場合、1 つのボトルネックが原因でスケーリングできない可能性があります。これは、問題にハードウェアをいくら投入しても、収益が減少するためです。
そうは言っても、スケーラビリティの問題には他の理由がよくあります。たとえば、ファイル アクセスやネットワーク アクセスのブロックなどです。これは、目にする内部計算よりもはるかに遅いため、プロファイリングは BigO よりも重要です。