big-o

0熱

2答えて

アルゴリズム - Little OとBig Omegaは同じ機能を持っていますか？

私はf(n),g(n)という2つの機能を持っています。f(n)=o(g(n))です。を明確にするために、私はそれはf(n)=Omega(g(n))ことを、私に与えられ、その情報を持つことも可能である oを少しについて取っています。私にはほとんど-Oの定義は for every c>0,f(n)<c * g(n). おかげと私に言っているので、それは、それは可能ではないということですね！

2熱

2答えて

HashSetを使用したO（1）ルックアップ時間の隣接リスト

私のアルゴリズムクラスでは、グラフ表示の隣接リストの引き戻しは、各ノードに対応する隣接ノードの配列を反復するO（n）ルックアップ時間であると言われています。私は自分の隣接ノードのHashSetにマップするHashMapを使って自分の隣接リストを実装していますが、O（1）ルックアップしか取らないでしょうか？私は行方不明のものがありますか？

0熱

2答えて

教科書のparticalur Big-Oの例を理解できません

これまでBig-O表記を理解しており、計算方法がわかりました...ほとんどの状況は分かりやすいです。しかし、私はこの1つの問題に遭遇しましたが、私の人生のためには理解できません。説明：式に最適なbig-O表記を選択します。 (n^2 + lg(n))(n-1)/(n + n^2) 答えはO（n）です。それはすべて罰金とダンディーですが、分子のn^3因子を考えれば、それはどのように合理化されて

0熱

1答えて

複数の関数呼び出しを持つ再帰関数の大きなO？

私はこの再帰関数の最悪のケースの時間計算量を決定する問題を抱えている： long f(int n) { if(n <= 0) return 1; else { return f(n/2) + f(n/2) + f(n/2); } } 私はあなたが一度だけF（N/2）を返すれた場合、それはO（n個のログを記録）になることを理解しています。だから私は3つ、

1熱

1答えて

ユーザ入力を伴うwhileループのためのBig-O

モジュールXがp単位の実行時間を必要とすると仮定します.pは定数です。次の各アルゴリズムの複雑さを求めます.nは入力データのサイズ、qは1より大きい正の整数です。時間の複雑さはどのようになりますか？対数関数の塩基がqある set i = 1 `while i ≤ n` `Module X` `i = q * i` endwhile

0熱

1答えて

再帰最小二乗（RLS）アルゴリズムの複雑さ

recursive least squares (RLS)アルゴリズムの複雑さはどの操作でO（n^2）に等しいのですか？その理由は何ですか？ % Filter Parameters p = 4; % filter order lambda = 1.0; % forgetting factor laminv = 1/lambda; delta = 1.0; % initi

1熱

1答えて

時間複雑さの演習（擬似コード）

ちょうど開始されたデータ構造。この1に捕まってしまった： Nの数が奇数か偶数であれば、それは変化しますので、私は、内側の中でとループのトラブルを抱えています。私の最高の場合はとなります - いくつかの助けを大好きだLOGN回（ベース2） - ループの内部には、LOGN（ベース2）回、そして、whileループを実行します。

1熱

5答えて

ビッグ・オア・マージ・ソート

マージ・ソートのためにビッグ・オーで講義をしましたが、私は混乱します。示されたものである： 0マージ[< ----- N -------->] = N 1マージ[<、-N/2-- [n/4] [n/4] [n/4] =（n/2 + n/2）= n/2] 2（N/4 + N/4）= N .... ログ（N）は、n = が合計=（N + N + N + ... + N）= LG N = O（nはn個

3熱

2答えて

配列が与えられた場合、各要素の最後の小さい要素を見つけよう。

配列を渡すと、各要素の最後の小さな要素の配列の配列を見つける。たとえば、指定された配列が{4,2,1,5,3}であるとします。次に、各要素の最後の小さな要素は次のようになります。 1対4-> 3 4->3 2->1 1->Null 5->3 3->Null 通知は、3より小さい4 得/出力アレイは要素自体のインデックスを持っていないであろう配列の最後の要素です。結果は{4,2,-1,

0熱

1答えて

ビッグああ分析

コード1：外側のループがn^2回とループの実行をn回の内側を走るので、 I私の意見このコードはO（N^3）です。私の専門家によると、このコードはO（n^3）ではありません。誰かが理由を説明できますか？私は本当に混乱しています。 i, j, sum = 1, 1, 0 while i < n**3: while j < n: sum = sum + i j += 1