time-complexity

11熱

3答えて

私はnの要素の配列を持っていますが、要素が1つしか繰り返されていない場合は、他のすべての要素が> 1回繰り返されます。配列内の数値の範囲に制限はありません。いくつかのソリューションは、次のとおりです。ハッシュを利用して、それは線形時間複雑になるだろうが、非常に悪い宇宙複雑マージO(nlogn)を使用して、リストをソートし、その要素を見つけます繰り返しはしませんもっと良い解決策はありますか？

7熱

3答えて

前処理

チェックとO 2つのツリーのノードが関連しているかどうかを確認し（祖先/子孫）（1）2つのツリーのノードが関連している場合（すなわち、祖先 - 子孫）（1）Oでそれを解決します時間とO（N）スペース（ノードN =＃）前処理は、それをだが許可されています。私は下の私の解決策（アプローチ）に行くつもりです。あなた自身を最初に考えたければ、やめてください。私は予約注文を行うことを決めた前処理のため

2熱

2答えて

複数ソートされた配列とその複雑さの検索

与えられた3ソートされた配列。 a + b = cとなるように、各配列から1つずつ3つの要素を探します。それはO（n^3）時間の複雑さよりも少ないことができますか？私を助けてください。

1熱

1答えて

マージソートの実行時間::すべての要素が同じです

すべての要素が同じサイズnの配列があるとします。何がO（n）になりますか？線形であろうか？

7熱

1答えて

HTML DOMルックアップの時間の複雑さは何ですか

クレイジーな最適化がないと仮定します（私はChromeを見ています）。私は生の、厄介な、壊れていない、つまり、v6のjavascriptの、それを修正していない、ということについて話しています。下限ビーイング：対 document.getElementById() ：ハッシュテーブルはのための完全なデータ構造であるとして document.getElementsByTagName('div

8熱

5答えて

ビットマップ内の連続領域をO（r * c）よりも向上させることができますか？

衛星によって撮影された表面の画像が与えられます。画像は水が「。」でマークされたビットマップです。土地には「*」と記されています。 '*'の隣接グループは島を形成します。（2つの '*'は、それらが水平、垂直または対角の隣接である場合に隣接する）。あなたの仕事は、ビットマップに島の数を印刷することです。例入力： - .........** **......*** ........... .

17熱

2答えて

接尾辞配列対接尾辞木

接尾辞ツリーが拡張接尾辞配列よりも優れている場合、私はちょっと知りたいです。 Replacing sufﬁx trees with enhanced sufﬁx arraysを読んだ後、私はもうサフィックスツリーを使用する理由はありません。いくつかのメソッドは複雑になることがありますが、接尾辞配列ですべてを行うことができます。接尾辞ツリーで何ができ、同じ複雑さが必要ですが、メモリは少なくて済みます

7熱

1答えて

random.sampleの時間複雑度

別のスレッドでは、バイナリヒープ重み付きランダムサンプルの時間複雑さがO（n * log（m））に等しく、ここでnは選択肢の数であり、mは数選択するノードの数。 Pythonでrandom.sampleとして使用されている重み付けされていないランダムなサンプルの時間的な複雑さが不思議でした。時間の複雑さは単にO（n）かそれとも完全に他の何かですか？

7熱

1答えて

set :: insertの複雑さ

私は、セット内での挿入操作はlog（n）時間しかかかりません。そんなことがあるものか？挿入するには、最初に、新しい要素が座っていなければならないソートされた配列内の位置を見つけました。バイナリ検索を使用すると、log（n）が使用されます。その位置に挿入するには、それに続くすべての要素を1桁右にシフトする必要があります。別のn時間かかる。私の疑問は、セットが配列として実装され、要素がソートされた

3熱

2答えて

アルゴリズムの再帰の分析

これは私のアルゴリズムクラスの古い宿題です。私はこの問題に対する解決策を持っていますが、繰り返し試みても、正しい方向にどのように考えて解決策に到達するのか理解できません。 function h(N) { if (N==1) return 3; else { sum = 1; i = 0; while (i < h(N-1)) s