問題タブ [big-o]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - アルゴリズムの最悪ケースの時間計算量
最悪の場合の時間複雑性 t(n) とは何ですか :- アルゴリズムに関するこの本を読んでいます。例として、T(n) を取得する方法 .... 選択ソート アルゴリズムのように
selectionSort(A[0..n-1]) を扱っているかのように
疑似コードを書いてみましょう
--------C#でも書きます---------------
==================
t（n）を取得する方法、または既知の最悪の場合の時間の複雑さ
time-complexity - フィボナッチ数列の計算量
Big-O 表記法は理解できますが、多くの関数で計算する方法がわかりません。特に、単純なバージョンのフィボナッチ数列の計算上の複雑さを理解しようとしています。
フィボナッチ数列の計算上の複雑さとはどのように計算されますか?
big-o - 内側のループの反復回数が外側のループの現在の反復によって決定される、入れ子になったループの Big-O とは何ですか?
次の入れ子になったループの Big-O 時間計算量は?
それでもO(N^2)でしょうか？
arrays - 値がソートされた配列にあるかどうかを判断するのにかかる時間は何ですか?
5000 個の整数のソート済み配列があります。ランダムな整数が配列のメンバーであるかどうかは、どのくらいの速さでわかりますか? 一般的な答えとしては、C と Ruby がいいでしょう。
配列値の形式は次のとおりです。
ここでc、1 から 5000 までの任意の整数を指定できます。
例えば：
big-o - Θ(n) と O(n) の違いは何ですか?
ときどき、途中に何かが入った奇妙な Θ 記号の Θ(n) を見たり、O(n) だけを見たりすることがあります。誰もこの記号を入力する方法を知らないので、単にタイプするのが面倒なのでしょうか、それとも別の意味でしょうか?
algorithm - 「Big O」表記の分かりやすい英語の説明は?
正式な定義はできるだけ少なく、簡単な数学を好む.
big-o - ネストされた for ループの時間計算量
次のコードの時間計算量を計算する必要があります。
O(n^2)ですか？
algorithm - のアルゴリズム速度順序
O（x）表記を使用してアルゴリズムの速度を推定しようとすると、完全にだまされることがあります。つまり、順序がO（n）またはO（mxn）の場合は実際に指摘できますが、O（lg（ n））またはO（C（power n））何かが足りないと思います...では、アルゴリズムをすばやく見落としながら簡単に見積もるためのヒントとコツは何ですか？
私が探しているものの例として、ここに簡単なもののいくつかがあります（間違っている可能性がありますが、最善を尽くしています）：
- O（n）：1からnまでの単純なループがある場合（またはそれらのいくつかであるが、ネストされていない場合。
- O（mxn）：制限がmとnである別の内部のネストされたループ。
前もって感謝します。
java - Java Collections Framework 実装の Big-O サマリー?
もうすぐ「Java クラッシュ コース」を教えることになるかもしれません。聴衆メンバーが Big-O 記法を知っていると想定するのはおそらく安全ですが、さまざまなコレクション実装でのさまざまな操作の順序が何であるかを知っていると想定するのはおそらく安全ではありません。
自分で要約マトリックスを生成するのに時間をかけることもできますが、それがすでにどこかで公開されている場合は、それを再利用したいと思います (もちろん、適切なクレジットを付けて)。
誰にも指針がありますか？
code-analysis - Big-O の複雑さについてコード分析を実行することを決定できるツールはありますか?
一般に、複雑な関数を分析する場合、定義する変数は 1 つまたは 2 つだけではないため、"n" を定義するのが難しいのではないかと思います。
循環的複雑度の分析ツールはありますが、時間 (および/または空間) 複雑度の分析ツールはありますか? もしそうなら、それはどれですか？そうでないなら、なぜですか？それは実行不可能ですか？不可能？誰かがそれに慣れていないだけですか？
理想的には、アプリケーションの全体的な複雑さのようなもの (さまざまな可能な "n" を定義する) と、アプリ内の各メソッドのようなものがあるでしょう。
編集：停止問題のために正確な解決策は不可能のようですが、ある種のヒューリスティックな近似は可能ですか? 実用的な目的では、優れたプロファイラーがはるかに有用な情報を提供することを認識していますが、それは興味深い問題のようです。
また、プログラムの特定のサブセットを計算するものはどうですか?