問題タブ [asymptotic-complexity]

IPとFPのパフォーマンスについて質問があります。n番目のフィボナッチ数を計算する関数があるとしましょう。

命令型プログラミングでは、反復法、再帰、または動的計画法を使用してn番目のフィボナッチ数を計算することを選択できます。もちろん、反復計画法と動的計画法は、漸近的に再帰する場合に比べてパフォーマンスが向上します。

関数型プログラミングでは、関係する状態がないと仮定すると、再帰的な方法でしか実行できません。

この場合、関数型プログラミングは、効率の点で（漸近的に）命令型プログラミングと比較して、常に同等または低速で実行されるという意味ではありませんか？

実際の関数型プログラミングはこの問題にどのように対処しますか？

Big O表記を使用して、forループの複雑さを理解しようとしています。私は以前に他のクラスでこれを行いましたが、これは実際のアルゴリズムに基づいているため、他のクラスよりも厳密です。コードは次のとおりです。

と

最初のループはリストをn回通過するため、O（n）の複雑さであることがわかりました。2番目のループに関しては、私は少し迷っています。テストされるnごとにi回ループを通過していると思います。私は（誤って）これは、ループが評価されるたびにループがO（n * i）であることを意味すると想定しました。私の仮定に欠けているものはありますか？cnt++は定数時間であることを私は知っています。

分析にご協力いただきありがとうございます。各ループは独自のスペースにあり、一緒ではありません。

アルゴリズムに 2 つのサブ アルゴリズムがある場合、与えられた入力に対してサブ アルゴリズム A1 が最良のケースである場合、サブ アルゴリズム A2 は最悪のケースです。全体的なアルゴリズムの複雑さを知るにはどうすればよいですか? 簡単に言うと、Ω(N) + O(N)=? アルゴリズムが順次実行されているかどうかは、全体の複雑さが O(N)+ O(N) であり、ネストされた順序で O(N)* O(N) であるかどうかを知っています。

シーケンシャルと入れ子の両方の場合について教えてください

Big O の複雑さの観点から、 低複雑度から高複雑度まで次の関数を並べ替えようとしています: 4^(log(N))、 2N、3^100、log(log(N))、5N、N!(log(N))^2

これ：

1. 3^100
2. log(log(N))
3. 2N
4. 5N
5. (log(N))^2
6. 4^(log(N))
7. N!

ウィキペディアで提供されているチャートを使用するだけでこれを理解しました。答えを確認する方法はありますか？

このメソッドは、 の配列内の少なくとも 2 つの値が である場合にhasTwoTrueValues戻ります。提案された 3 つの実装すべてについて、Big-O の実行時間を提供します。truebooleantrue

//バージョン 1

//バージョン 2

//バージョン 3

これらは私の答えです：

• バージョン1はO(n)
• バージョン2はO(n^2)
• バージョン3はO(n^2)

私はこの Big-O 記法に本当に慣れていないので、答えが正しいか間違っているかについてのガイダンスが必要です。もし私が間違っていたら、説明して、私が学ぶのを手伝ってくれませんか?

この T(n) = 2T( n/2 ) + n lg n再帰方程式のマスター定理を解くことができますか? 私は、3ree ケース条件のいずれも満たさないため、ここでマスター定理を適用できないと彼が述べているリンクから来ています。一方、彼は別の例 T(n) = 27T(n/3) + Θ(n^3 lg n) を取り上げ、閉じた解を見つけましたtheta(n^3logn) 。これを解決するために、マスター定理の 2 番目のケースを使用If f(n) = Θ(nlogba (lg n)k ) then T(n) ∈ Θ(nlogba (lg n)k+1) for some k >= 0 しました。ここで、2 番目のケースに完全に適合するのに、ここで 2 番目のケースを適用できないのはなぜでしょうか。 私の考え: a = 2 , b =2; let k =1 then f(n) = theta(n^log_2 2 logn) for k= 1 so T(n) = theta(nlogn) しかし、彼がこれについて述べたように、マスター定理を適用することはできません。 .

注: これは inおよび in の f(n) bcz によるものです* * ここで間違っている場合は訂正してください。T(n) = 2T( n/2 ) + n lg n f(n) = nlog nT(n) = 27T(n/3) + Θ(n^3 lg n)f(n) = theta(n^3log n)

ここvar_dumpに私の配列があります：

(ただの楽しみのために、このコードに 2 つの駄洒落を含めました。探してみてください!)

この配列を 2 つの配列に分割するにはどうすればよいですか。一方にはすべてのquacks が含まれます。他のAaaaarrrrrggggghhhhh？

常に連続した順序であるとは限らないことに注意してください。そのため、次のようなネストされたハッシュマップを考えていました。

1. 小切手if (isset($myarr['$found_val']))
2. 見つかった場合はその配列を追加します
3. それ以外の場合は、新しい配列でその場所を作成します

しかし、配列がどのように実装されているかわからないので、O(n) を追加する可能性があります。その場合、他の解決策が必要になります...

特定の深さdまでの完全な二分木があると仮定します。このツリーをトラバース（プレオーダートラバーサル）するのにかかる時間計算量はどれくらいですか。

ツリー内のノードの数が2^dであることがわかっているため、混乱しています。したがって、時間計算量はどうなるでしょうBigO(2^d)か。木が指数関数的に成長しているからです。

しかし、インターネットで調査したBigO(n)ところ、トラバーサルとは、nが要素の数（2^dこの場合は）でありBigO(2^d)、何が欠けているのかではないと誰もが述べています。

ありがとう

私は二分木と配列リスト表現についていくつかの研究を行ってきました。最悪の場合の空間の複雑さが O(2^n) であることを理解するのに苦労しています。具体的には、この本では、スペースの使用量は O(N) (N = 配列サイズ) であり、最悪の場合は O(2^n) であると述べています。各ノードには O(2^n) ではない 2 つの子 (インデックス) があり、n = no であるため、最悪の場合は 2n になると考えていました。要素の。

たとえば、7 つのノードを持つバイナリ ツリーがある場合、スペースは 2^n = 128 ではなく 2n = 14 になります。

入力が単なる数値で、出力が除数のセットであるアルゴリズムがある場合、入力は常に1つの数値になり、アルゴリズムの反復回数は数値の大きさによって異なります。そのようなアルゴリズムの大きな表記法は? アルゴリズム：