-4

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

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

実際の質問

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

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

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

私の回答/入力:

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

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

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

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

4

4 に答える 4

2

ソートされていない場合とソートされている場合。私がやる、それならあなたは本当に宿題をする必要がある

Stackoverflowマークアップには、これを行うためのテーブルが本当に必要です。ソートされていない/配列、ソートされた/配列、ソートされていない/リンクされたリスト、ソートされた/リンクされたリストの操作がどれほど「高価」であるかを言いたい

最後のポイント：「アプリケーションの速度」は、個々の操作の速度以上のものを考慮するためのヒントです。

* Adding

並べ替えなし：サイズ変更が必要でない限り、配列の追加はO（1）です。最後に追加するだけです。オーバーヘッドを最小限に抑えるサイズ変更戦略について話し合うことをお勧めします（ヒント：サイズを1つ増やすだけではありません）

並べ替え：配列の追加はO（n）です-追加する場所を見つけるのはO（log（n））ですが、新しい要素のrommを作成するには、要素の半分を（平均して）上に移動する必要があります

未ソート：リンクリストはO（1）です-リストの最初または最後に追加します。

並べ替え：リンクリストはO（n）です-O（1）に要素を再度追加できますが、リストを配置する場所を見つけるには、平均してリストの半分をスキャンする必要があります。

それで、残りのためにあなたに渡りなさい。答えを投稿してください、そして私たちはそれを批評します、しかしあなたの（おそらく）高価な教育を最大限に活用するために、あなたは本当にこれにいくつかの仕事をする必要があります:)

* Removing
* Retrieving
* Sorting
* Overall speed
* Overall memory usage
于 2008-11-09T19:34:46.373 に答える
2

これがどのクラス向けなのかはわかりませんが、CS プログラムの場合は、「遅い」と「速い」よりもうまくやる必要があります。必要な操作数という観点から、それを定量化してみてください。このような定量化に通常使用される機械に精通している必要があります。その機械を使用してください。

于 2008-11-09T18:59:19.300 に答える
0

@ポール：ありがとう

  • 削除

ソートされていない＆ソートされている：配列の削除はO（n）です-「穴」を埋めるためにすべての要素を移動する必要があります

ソートされていない＆ソートされている：リンクリストはO（1）です-必要に応じてポインタを変更します

于 2008-11-09T19:45:32.793 に答える