問題タブ [space-complexity]

Russell と Norvig で与えられたアルゴリズムと計算の理解が正しいかどうかを確認したかっただけです。

宣教師と人食い人種を問題として使用して、時間と空間の複雑さをテストしています。深さの計算はそれほど大したことではありません。私はいつも深さ 11 で解を見つけます。頭を包み込めないのは、分岐要因です。

Russell と Norvig の 82 ページには、次のように書かれています。

「O(b^(d-1))探索セットにはO(b^d)ノードがあり、フロンティアにはノードがあります...」

私のプログラムは8502、探索されたセット内の14006ノードとフロンティア内のノードを表示します。

私の思考プロセスは次のとおりですd。Russell と Norvig に従ってノードの数とルートを取得すると、分岐係数が何であるかを取得する必要があります。今、自分の考えが正しいかどうかわかりません。私はちょうどそれを思いつきました。

したがって、 の 10 乗根 (d-1)を取って (およそ) を8502取得2.47し、 の 11 乗根 (d) を取って(およそ)14006を取得し2.39ます。したがって、私の結論は、分岐係数 b はおおよそ2.43.

私はまったく的を射ていますか、それとも完全に間違っていますか? これは、私が今羽ばたいているものの1つです。しかし、私が間違っているか正しいかを知りたいです。

問題の複雑さを評価する際に、私はいつも問題を抱えています。私は通常、O(n) ソリューションを見つけようとしますが、O(nlogn) または O(n^2) が可能な限り最良のソリューションである場合もあります。

私が知っている「経験則」の 1 つは、ソートされた配列があり、何かを見つける必要がある場合、おそらく O(logn) で実行できるということです。また、ソートは O(nlogn) よりも速く実行できないことも知っています。経験の浅いプログラマーが従うことができる同様のルールはありますか? 再発する問題の複雑さを知っていますか?

私にとって最も厄介なのは O(n^2) です。特に、試験のプレッシャーにさらされていて、より良い試験を探すことに時間を浪費している場合はなおさらです。

これがあまりにも広範で意見に基づく質問ではないことを願っています。

ありがとう！

ハッシュテーブル、辞書などについて読んでいます。私が見たすべての文献とビデオは、ハ​​ッシュテーブルが空間/時間のトレードオフ特性を持つことを暗示しています。

ハッシュテーブルが、同じ数の要素 (値) を持つ配列やリストよりも多くのスペースを占有する理由を理解するのに苦労していますか? ハッシュ化されたキーを実際に保存することと関係がありますか?

私が理解している限り、基本的な用語では、ハッシュテーブルはキー識別子（文字列など）を取り、それをハッシュ関数に渡します。ハッシュ関数は、インデックスを配列または他のデータ構造に吐き出します。オブジェクト (値) を配列またはテーブルに格納するための明白なメモリ使用量とは別に、ハッシュ テーブルがより多くのスペースを使用するのはなぜですか? 明らかな何かが欠けているような気がします...

配列に関連する問題があります。要件は、時間の複雑さが O(n) で、空間の複雑さが O(1) であることです。

をArrays.sort(arr)使用し、forループを 1 つのパス ループに使用すると、たとえば次のようになります。

}

したがって、ループには O(n) 時間がかかります。私の質問は次のとおりArrays.sort()です。より多くの時間がかかりますか? を使用した場合Arrays.sort()、この時間の複雑さは O(n) のままでしょうか? そして、Arrays.sort()より多くのスペースがかかりますか?

重複を排除するために、上記の単純なコードのスペースの複雑さをチェックしてください。

1. セット内のストレージ -> O(n)
2. set.toArray により生成された配列内のストレージ - O(n)
3. 新しく作成されたリストのストレージ - O(n)

合計 O(3n) は O(n) と同じです。

これを確認してもらえますか？

このアルゴリズムは、一般的な二分木をレベルごとに出力するためのものです。

printSpecificLevel_BT()と の時間計算量と空間計算量はprintBT_LBL()?

printSpecificLevel_BT時間の複雑さはO(lg N)で、空間の複雑さはだと思いますO(lg N)。時間の複雑さはで、空間の複雑さは
だと思います。printBT_LBL()O((lgN)^2)O((lgN)^2)

これは正しいです？