問題タブ [space-complexity]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
c# - Dictionary の時間と空間の複雑さとは何ですか?
サイズ N (ieN 要素) のデータがあり、ディクショナリが容量 N で作成されたとします。複雑さは次のとおりです。
- スペース -- 辞書全体
- time -- 辞書にエントリを追加
MS は、エントリの検索が O(1) に近いことだけを明らかにしました。しかし、残りはどうですか？
c++ - 初期化されたポインター データ構造のスペースの複雑さ
質問があります。
理論的なコンピューター サイエンスの観点から、アルゴリズムを分析するときに、アルゴリズムが新しいデータ構造を初期化する場合、そのデータ構造を空間の複雑さの一部と見なします。
今、私はこの部分についてあまり確信が持てません。
の配列を持っていて、ポインターintのマップを使用してそれらをマップしたいとしましょう。intそのような
このアルゴリズムがポインターを使用していない場合、サイズ n でマップを初期化していることを明確に述べることができます。したがって、スペースの複雑さは O(n) ですが、ポインターを使用しているこの場合、スペースの複雑さはどうなるでしょうか。このアルゴリズムの？
data-structures - 動的配列の最適な成長係数を計算する数学的な方法はありますか?
クラス プロジェクトの場合、巡回動的配列に基づいて優先キューの最適な成長係数を見つける必要があります。いくつかのテストを実行しましたが、決定的ではありませんでした。それを示す数学的な方法があると言われましたが、どこにも見つかりませんでした。
少し調べてみたところ、Java ArrayList が 3/2 を使用していることがわかりました。また、9/8 係数を使用する pyhton のリストの ac 実装もあり、基本的には異なるプログラミング言語間で異なると思います。
では、動的配列の「最適な」成長率を見つける数学的な方法はありますか?
java - TreeRangeMap の時間と空間の複雑さ
プロジェクトのニーズに非常に適していると思われるTreeRangeMapをグアバしようとしています。java docs は、get、put、および next の時間が O(log(n)) である (Java 標準 ?) TreeMap に基づいていると述べています。
ただし、TreeRangeMap は、このSO の質問によると、クエリの O(k + log(n)) 時間の複雑さ、O(n) スペース、k が範囲サイズである、ある種の範囲ツリー実装である必要があります。誰かがこれを確認できますか？
TreeRangeMap.subRangeMap()操作の時間の複雑さにも非常に興味があります。同じ O(k + log(n)) を持っていますか?
ありがとう。
algorithm - アルゴリズムのメモリと時間の複雑さを決定する方法は?
私は時間とメモリの複雑さを判断するのが苦手で、誰かが私を助けてくれれば幸いです.
ここにアルゴリズムがありますが、その時間とメモリの複雑さがどうなるかわかりません。
その時間とメモリの複雑さとは何ですか?またその理由は?
ありがとう
space-complexity - Ids アルゴリズムの空間複雑度
こんにちは、IDS (反復深化深さ優先検索) アルゴリズムの空間の複雑さを計算しようとしていますが、その方法がわかりません。必要なスペースを計算できるように、アルゴリズムがツリーのノードをどのように訪問するのか、私にはよくわかりません。手伝って頂けますか？