ソートされたリンクリストの実行時間

要素を見つけて要素を挿入し、ソートされたリンクリスト内の要素を削除する実行時間とは何ですか？ソートされたリンクリストの実行時間

私はあなたが関係なく各リンクを通過する必要があるので、彼らはすべてO（n）だと思っています。私は正しい？

2016-11-18 Hello World

ここをクリックhttp://bigocheatsheet.com/ – duncan

@duncanソートされたリンクされたリストはそこにありません –

特定の要素を見つけるために挿入と削除が必要になります。つまり、彼らは検索と同じことをしているので、両方ともO（n）になります。 – duncan

はい、あなたは正しいです。ノードの順序を知っているかどうかにかかわらず、実際にどのノードにもアクセスする唯一の方法は、その前のノードを経由することです。これは、N個のノードに対して、N個のノードを経由して操作O（N）を行わなければならないことを意味します。

出典

2016-11-18 21:47:09 Jay

N/2ノードを経由するだけです。したがって、ソートされたリンクされたリストは、同じ複雑さのクラスに属しているが、因子は2倍低い。 – bipll

これは当てはまりません.1つのノードをたどるたびに2つのノードを削除すると、O（N/2）または時間の複雑さしか得られないことに注意してください。これはここでは当てはまりません。リスト内を移動するたびに、ONEノードのみが削除されます。最悪のシナリオ（あなたが考慮する必要がある）を仮定すると、時間の複雑さはO（N）です。 O（N）は常に平均的なケースではなく、問題のアルゴリズムがO（x）よりも時間がかかりませんと自信を持って言いたいと思います！ – Jay

ソートされたリンクリストの実行時間

答えて

関連する問題