問題タブ [big-o]

どうやら ;-) 標準コンテナは、何らかの保証を提供します。

どのような種類の保証があり、さまざまな種類のコンテナーの違いは正確には何ですか?

SGIページ（STLについて）から作業して、私はこれを思いつきました：

アルゴリズムの時間の複雑さについて話すとき、「一定の償却時間」とはどういう意味ですか?

リストへの変更のリストがあります-追加と削除。リストは非常に大きくなる可能性があります。たとえば、10,000 アイテムです。

変更後のリストの状態を知りたい 9'000.

リストを最初から9'000に変更するまで歩くことができました。それは私には少し長すぎるようです。

アイテムのリストを保持し、アイテムが追加されたときと削除されたときに記録し、このリストをたどって、特定の変更でリストに何があるかを確認できます。Adds と Deletes の可能性が同じである場合、実行する必要があるリスト要素の数は半分になります...

しかし、Big O 表記法では、問題のサイズを半分にしても効率が良くなることはありません (私の理解が正しければ)。

100 回目または 1000 回目の変更ごとにリストの状態をキャッシュすることもできますが、繰り返しになりますが、アイテムの数を 'n' で割っても効率が良くならないということです。

では、これを行う効率的な方法は何ですか？これを行う効率的な方法はありますか？

詳細: 具体的には、カスタム アロケーターでのメモリ割り当て/割り当て解除を追跡しています。各割り当て/解放は、リスト内のイベントです。各割り当てには一意の ID があります。(例) 9'000 イベントの後に現在割り当てられているものを知りたいです。

私の最初のアイデアは、IDごとに、割り当てられたイベントと割り当て解除されたイベントを保存することでした。次に、割り当てイベントが 9000 より大きい最初の割り当てまで、このリストをたどります。

私はマイク F が指摘した点が好きです - 最も近い 100 番目のアイテムから歩くのは一定の時間です...

私は最近、再帰と Big-O 記法を含むコンピューター サイエンスの宿題に取り組んでいます。私はこれをかなりよく理解していると思います (ただし、完全ではないことは確かです!)。奇妙なことに、それを見ると、宿題の中で最も単純なもののように見えます。

次の再発の解決策として、big-Oh 表記法を使用して最高の成長率を提供してください。

T(1) = 2

T(n) = 2T(n - 1) + 1 for n>1

選択肢は次のとおりです。

• O(n log n)
• O(n^2)
• O(2^n)
• O(n^n)

大きな O が上限として機能し、プログラムまたはプロセスにかかる最大の計算量または最大実行時間を表すことを理解しています。この特定の再帰は O(n) であるべきだと思います。なぜなら、再帰は n の値ごとに 1 回しか発生しないからです。n が利用できないので、他の 3 つのオプションである O(nlogn) よりも良いか、悪いかのどちらかです。

だから、私の質問は: なぜこれは O(n) ではないのですか?

宿題として、次の 8 つのコード フラグメントを与えられ、実行時間を分析して Big-Oh 表記にしました。私が正しい軌道に乗っているかどうか誰か教えてください。

フラグメント1のO（N）を考えています

フラグメント 2 についても O(N)

フラグメント 3 の O(N^2)

フラグメント 4 の O(N)

フラグメント 5 の O(N^2) ですが、n * n は私を少し混乱させているので、よくわかりません

フラグメント 6 についても O(N^2)

フラグメント 7 の O(N^3) ですが、もう一度 n * n が私を失望させています

フラグメント 8 の O(N)

次の場合の STL マルチセット、マップ、およびハッシュ マップ クラスの Big O 表記の複雑さを知りたいです。

• エントリの挿入
• エントリへのアクセス
• エントリの取得
• エントリの比較

std::list::size()最近、線形の複雑性があると言及している人がいることに気付きました。一部の情報源
に よると、これは実際には実装に依存しているため、標準では複雑さがどうあるべきかが規定されていません。このブログエントリ のコメントには次のように書かれています。

実際には、使用している STL によって異なります。Microsoft Visual Studio V6 は size() を {return (_Size); として実装します。} 一方、gcc (少なくともバージョン 3.3.2 および 4.1.0 では) は { return std::distance(begin(), end()); のように行います。最初の速度は一定で、2 番目の速度は o(N) です。

1. したがって、私の推測では、VC++ クラウドsize()は常に複雑であり、Dinkumware はおそらく VC6 以降その事実を変えていないでしょう。私はそこにいますか？
   
2. 現在はどのように見えますgccか? それが本当に O(n) である場合、なぜ開発者はそうすることにしたのですか?

O（n）の長さnのソートされていない配列でk番目に大きい要素を見つける方法があると思います。または、おそらくそれは「期待される」O(n)か何かです。どうすればこれを行うことができますか？

LinkedLists と Arrays を比較しながら、並べ替えられたデータと並べ替えられていないデータとの違いを比較する

• 追加する
• 削除する
• 取得中
• 並べ替え
• 全体の速度
• 全体的なメモリ使用量

実際の質問

ソートされていないデータセットを配列ではなく連結リストとして実装する可能性について議論してください。アプリケーションの挿入、削除、取得、コンピュータのメモリ、および速度に関して、どのようなトレードオフがありますか?

並べ替えられたデータセットを配列ではなく連結リストとして実装する可能性について議論してください。アプリケーションの挿入、削除、取得、コンピュータのメモリ、および速度に関して、どのようなトレードオフがありますか?

前の質問への回答に基づいて、アプリケーションでリンク リストを使用するコストと利点を要約します。

私の回答/入力:

LinkedLists は、新しいノードが追加されるたびにメモリを割り当てる必要があります。これは、多くのノードを追加してサイズが変化し続ける場合に便利ですが、少数の要素を追加する場合は一般的に遅くなります

プログラムの実行の開始時に配列にメモリが割り当てられ、リストのサイズ変更が遅くなります（サイズ変更が必要な場合、多くの要素の追加が遅くなります）

インデックス付けにより、配列での取得が高速になります

ポインターによる LinkedList での追加/削除の高速化

範囲の交差は単純ですが、重要な問題です。

それはすでに2回答えられています：

• 番号範囲の共通部分を検索
• 日付範囲の比較

最初の解決策はO（n）であり、2番目の解決策はデータベース用です（もちろんO（n）未満です）。

私は同じ問題を抱えていますが、nが大きい場合、データベース内にいません。

この問題は、長方形内のポイントをすばやく取得するための2Dポイントの保存と非常に似ているようですが、どのようにマッピングされるかわかりません。

では、範囲の検索のコストがO（n）未満になるように、範囲のセットをどのデータ構造に格納しますか？（Javaで利用可能なライブラリを使用するための追加のクレジット）

編集：

交差するすべての範囲のサブセットを取得したいのですが、検索範囲が複数の範囲と交差する可能性があることを意味します。

JavaでO（n）未満である必要があるメソッドは次のとおりです。

Rangeは、intの開始と終了のペアを含む単なるクラスです。

これは不可能な質問ではありません、私はすでに解決策を持っています、私はそれを行うためのより標準的/より簡単な方法があるかどうかを見たかっただけです