問題タブ [asymptotic-complexity]

n と x に依存する特定のアルゴリズムの実行時間 O(n, x) = Theta(n, x) を大量 (> 100) の例 (アルゴリズムが n と x にかかる時間) で計算したい）。実際にこれを行う方法はありますか？

n と x (!) が増加すると実行時間が増加することはわかっていますが、n または x mac は n ^ x のように増加するため、コヒーレンスが複雑すぎて「手」で O(n, x) を把握できないと思います。さらに悪い。

ところで。この問題を解決するために私が最も好む言語は、Python または PHP です。

次のアルゴリズムの時間計算量を知りたいです。一見したところ、時間の複雑さは O(n^5) のように見えます。これは、私がインターネットで見たサイトの大部分で言及されていることです。しかし、注意深く分析すると、別の答えが得られるようです。コードは次のとおりです。

walk me throughこれらの実行時間を見つける方法について誰か教えてください。については、 2 回の再帰呼び出しによるものfooだと思います。O(n^2)それΘ(n^2)もあるでしょうか？

についてbarは、無限再帰なのでわかりません。

次のアルゴリズムを検討してください。

このアルゴリズムが実行する加算演算と乗算演算の数を調べることに興味があります。しかし、私は困っています。i の値が反復ごとに 2 倍になることは理解していますが、アルゴリズムを一般化して n の値までの正しい数の演算を与える方法がわかりません。誰かがこの問題に光を当てることができれば、私はそれを大いに感謝します.

ありがとうございました！

このリンクでわかるように：http：//en.wikipedia.org/wiki/D-ary_heap#Applications ウィキペディアでは、dの最適な選択はd = m / nであると述べています（これにより、合計時間計算量がO（m logm / nn））

この推測は薄い空気から引き出されたように私には思えます。これが本当に最適なdであることを証明する（または説明する）簡単な方法はありますか？

前もって感謝します

面接の準備をしているときに、次の問題が見つかりました。

3は1+1 + 1、1 + 2、2+1と書くことができます。4は、1 + 1 + 1 + 1、1 + 1 + 2、2 + 2、1 + 2 + 1、2 + 1 + 1、3 + 1、1+3と書くことができます。整数が与えられた場合、可能な式はいくつ存在しますか？（1+2と2+1は異なります）

したがって、これは、それを計算し、それを実行するすべての数値のセットを取得するためのブルートフォースアルゴリズムを作成するのはかなり簡単です。

このアルゴリズムの複雑さを表す漸化式は次のとおりです。

この漸化式から大きな複雑さに到達する方法がよくわかりません。また、質問に対する閉じた形の解があるかどうかも知りたいです（各番号に対してそのような組み合わせがいくつあるか）。

また、各呼び出しの結果をキャッシュしてこのアルゴリズムをメモ化した場合の複雑さもわかりません（フィボナッチを高速化する方法と同様）。

3 つの PHP 配列内ですべての「ペア」と「トリプレット」を見つける方法がわかりません。私の配列は次のようになります。

これらの配列は 3 つあります。これらは常に整数キーでソートされ、常に 10 個のインデックス (0 ～ 9) が含まれます。私がやろうとしていることは次のとおりです。

• 2 つの配列または 3 つの配列すべてで (「サニタイズされた」フィールドを比較して) 同一の名前のインスタンスを見つけ、それらの「色」を同じになるように変更します (つまり、3 つすべての交点だけを見つけたくありません)。配列 - array_intersect で実行できます)
• すべてのエントリを結合し、同じ名前を (「サニタイズされた」フィールドを比較して) 重みを合計して結合する 4 番目の配列を作成します (色は関係ありません)。
• これらのタスクは似ているため、同時に実行し、複雑さを最小限に抑えたいと考えています

これは説明が難しいので、視覚的に表現しました。

色：

色 http://www.tsiomenko.com/1.png

重み:

ウェイト http://www.tsiomenko.com/2.png

私はいくつかの実用的なコードを持っていますが、それは本当に長くて醜く、N^3 のような複雑さがあります - ネストされた for ループを使用して、必要なものが得られるまですべての配列を複数回トラバースします。私は非常に小さな配列で作業していますが、他の人がこの問題にどのようにアプローチするのか興味があるので、これを効率的に行う方法を知りたいです。PHP の代わりに、この問題へのアプローチ方法に関する疑似コードを歓迎します。

私は試験の準備をしていますが、これらは昨年の試験の問題の一部です。タスクは、正確な複雑さと漸近的な複雑さの両方を計算することです。どのように解決しますか？可能であれば、普遍的に。

前もって感謝します

次の関数の複雑さを計算しようとしています:

具体的には、while ループの複雑さです。g(n) の複雑さは O(n) だと言われましたが、その複雑さがどの程度になるのか、どのように解決するのかわかりません。複雑さがO（0.5n ^ 2）ではないことに気づきましたが、毎回半分になるため、計算方法がわかりません。誰にもアイデアはありますか？

私はMaster Theoremを少し更新していますn.2つのサイズのサブ問題を再帰的に解決n-1し、ソリューションを一定時間で結合することにより、サイズの問題を解決するアルゴリズムの実行時間を把握しようとしています.
式は次のとおりです。
T(N) = 2T(N - 1) + O(1)
しかし、マスター定理の条件をどのように定式化できるかわかりません。つまり、この場合のマスター定理の式は
ありませんか? はいの場合、明らかにそれ以降であり、これをどのように理解できるかのベースはどこにありますか? 私がこれまでのところ正しいと仮定しますか？T(N/b)bb=N/(N-1)
a > b^kk=0O(N^z)z=log2(N/N-1)