フロントエンドの円形リンクリストに要素を挿入するアルゴリズムの複雑さ
-
16-10-2019 - |
質問
円形のリンクリストでは、[ヘッドを指しているノードの直前]の前に要素を前に挿入する必要がある場合は、o(1)で実行できます(回答を参照してください ここ)
しかし、現在の本では、O(n)(通常の方法)で行われていると言われています。また、講義PPTはほとんど見られませんでしたが、それらはすべて、リストを通過して要素を追加する通常の方法に言及しています。
私の質問は次のとおりです。
実際のシナリオでは、どの方法が使用されていますか?
私はMCQで構成される試験に出席しようとしています。上記の質問が尋ねられた場合、それは標準的な答えだからです。
解決
実際のシナリオで使用される方法は、シナリオ(およびプログラマー)に依存します。実装の選択に影響を与えるいくつかの可能な問題があります。
- アルゴリズムがプログラマーに知られているかどうか。
- コーディングの容易さ(使用できる一部のライブラリに既に実装されている場合、最も簡単です)。
- 速度 - それはデータ構造の使用方法によって異なります。
- データ構造によって採取されたスペースのオーバーヘッド。
インテリジェントなプログラマーは、これらすべてを考慮に入れ、さまざまなアルゴリズムとデータ構造をより知識が豊富にしようとする必要があります。
所属していません cs.stackexchange