かなりシンプルだと思いますが、私は自分自身を悩ますようです。2つのネストされたループの単純なアルゴリズムの複雑さ
次のどれが複雑ですか？
// let's say that Q has M initial items
while Q not empty
v <- Q.getFirst
for each z in v // here, every v cannot have more than 3 z's
...
O(1) operations here
...
Q.insert(z)
end
end
この現象が発生する回数、ある時点でVのは持っていない場合、依存するよりZの
が複雑Oです（のはこの数Nを呼びましょう）（M×N個^ 2）またはI 「間違ってる？これは、M個の親ノードを持つツリーを持つようなものであり、各ノードは最大でも3個の子を持つことができます。 Nはノードの総数です。
あなたのアルゴリズムの複雑さは、O（M * v） - 子ノードである親ノードの上限を持つべきです。これはO（n）と書かれています。ここで、nはツリー内のノードの数ですツリーを一度しか反復しません。
操作によっては、検討する価値のあるデータ構造によってはQ.insert(z)とQ.getFirst()の実行時間を考慮する必要があります。
ランタイムがO（1）であると仮定すると、O（M * v）は近似バウンディングですが、v要素を繰り返すことができるので、ランタイムがO ）O（m * v）はすべてのケースで実際に上限を過大評価するためです。 O（n）はツリーのすべてのインスタンスに対して正確です（nはノードの数です）。
私はあなたの挿入物の正確な実装を知らないので、O（n）と呼ぶのがはるかに安全だと言いますが、リンクされたリストではinsertとget firstがO（1） 。 （十分な情報が提供されていない場合、ほとんどのバイナリツリーの挿入はO（log n）になります）。それを投げて、その余分な変数が不要に見えるかもしれません。
HTH
に編集：コメント欄に問題の明確さは、私はより良い質問、固定ナンセンス
実際には逆もありますが、MはNよりかなり小さくなります。また、何かより多くのことが考えられます：あなたはN個のノードを持ち、そのうちのM個を前述のツリーの親ノードとみなすことを検討してください。だから、MはちょうどN（私はM = 1かM = Nが最悪のケースか分かりません）の小数です。 – foxTox
あなたは単数のツリートラバーサルをしているなら、あなたの質問にあなたのコメントに記載されているように、キューのテールリファレンスを保持することで達成することができます）、O（1）の実装を縮小することができます。 ）複雑さ。これは、ツリーのすべてのノードをルートから子へのキューに追加しようとしていることを前提としています。あなたのアルゴリズムの擬似コードを読んで、私はあなたがやろうとしていることは確かではありません。私は子供たちの再帰的反復は見ません。 – dddJewelsbbb
よく、擬似コードの場合、zはvの子であり、Qキューに挿入されます。複雑さについては、確かにそれは単一のツリートラバーサルですが、Mの最初の親ノードの集合が複雑さを変えてO（MxN）かO（N^2）かO（MxN^2） – foxTox
あなた 'Q.getFirst'とあなたの' Q.insert（Z） 'の複雑さとは何かを理解して助けましたか？ –
アレイ、キュー、またはスタックの場合はそれほど重要ではないので、配列を選択します。 O（1）を挿入し、O（n）を挿入する場合 – foxTox
hm ..スタックの最後に何かを挿入して最初に何かを取得すれば、FIFO関数に似ています。複雑さはO（1）とみなされるか、例えば両方の配列にあるC++実装は、O（n）の複雑さとみなされますか？ – foxTox