big-o

0熱

1答えて

O(N + logN)があるときは、非支配的な用語としてlogNをドロップします。 O(N + M)の場合、これらの用語は無関係であるため、両方の用語を保持する必要があります。 O(N + logM)のようなものはどうなりますか？一方で、用語はまだ無関係です。一方、Mが非常に大きく、Nが非常に小さい場合でも、Nは遅かれ早かれlogMを上回るので、おそらくNを支配的な用語とみなすべきです。この場合、

0熱

2答えて

完全なグラフの幅優先探索の複雑さは何ですか？

BFSの複雑さは、線形すなわちO（V + E）であると言われているが、有向完全グラフのエッジの総数は、V *（V-1）グラフ。だから、BFSはO（V^2）時間をかけて完全なグラフをたどるでしょうか？

0熱

1答えて

再帰的および末尾再帰的コードの実行時および領域の複雑さ

一連の数値のすべての部分集合を見つけるための以下のコードの複雑さは何ですか？ public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> subsets = new ArrayList<>(); subsets.add(new ArrayList<Integer>()); return

4熱

2答えて

SymPy級数展開

で混合可変用語を削除SymPyシンボルeとiの二つの機能を検討：これは、しかしながら z = e**3*i**3 + e**3*i**2 + e**3*i + e**3 + e**2*i**3 + e**2*i**2 + e**2*i + e**2 + e*i**3 + e*i**2 + e*i + e + i**3 + i**2 + i + 1 を生成eとiが共に小さいことを想定します fr

0熱

2答えて

再帰関数の時間と空間の複雑さを決定する

def foo(n): def bar(n): if n == 0: return 0 else: return 1 + bar (n - 1) return n * bar(n) fooの実行時間の複雑さは、入力nの観点からどのように計算できますか？空間の複雑さはどうですか？

0熱

1答えて

この定理をマスター定理なしで解く。バックトラッキングアルゴリズム

バックトラックアルゴリズムを作成しました。私はこのAlgoの複雑さが何であるかを尋ねられました。私は方程式がT（n）= 2T（n-1）+ 3（n_hat）であることを知ります。ここで、n_hatは最初のnです。それは各ステップで減少しないという意味です。私はこのことを計算するとかなり失われているということです。私はそれが約2 ** n *何かと信じています。しかし、私の計算はちょっと混乱して

0熱

1答えて

平均ケースBig Oとソートの影響

Stringにすべての一意の文字が含まれているかどうかを判断する方法の実装には、時間の複雑さがあります。基本、強引、アプローチが見文字のHashSetを維持する時にString 1文字を反復処理することです。反復の各文字について、Setに既にそれが含まれているかどうか確認し、そうであればfalseを返します。 String全体が検索された場合は、trueを返します。これは最悪の場合の複雑さとして

0熱

1答えて

ハッシュテーブルO（1）償却またはO（1）平均償却？

この質問は少し賢明かもしれませんが、私は本当に償却分析に深く浸透しようとしていますが、なぜハッシュテーブルの挿入がO（1）償却されているのか混乱しています。この定義を使用すると、「償却分析は、最悪の場合の各操作の平均パフォーマンス（時間をかけて）を示します」。ハッシュテーブルへのN個の挿入が最悪の場合のように、すべての操作で衝突が発生するようです。ユニバーサルハッシングは、負荷バランスが低く保た

0熱

2答えて

2つの条件を持つループのbig O計算

以下は、geeksforgeekからの最も近い対のポイントのコードスニペットです。コメントに見られるように、関数はO（n^2）ではなく線形で実行されると言います。それは第二のループは、一定の時刻に実行することができるからである。ここでは for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j) は私の質問です：この