0
実際の質問は以下の通りです。挿入の時間複雑度ソート基準。 Based Linked-List？
"参照ソートが参照ベースのリンクリストで行われた場合の時間の複雑さは何ですか？"
私はそれがO（1）だろうと思います、そうですか？ PREVIOUSが見つかるまでノードをチェックするので、ノードをAFTERしてからポインタを設定すれば良いです。したがって、すべてのノードをチェックする必要はないので、O（n）にすることはできません。
'O（1）'は、ソートに要する時間が、ソートしているものの数とは無関係であると言います。 10のものをソートすることは10兆のものと同じ時間がかかります。それは私には分かりません。 – phs
どの表記法を使用すれば、指定された範囲でソートするだけでよいのでしょうか？すべてのノードをチェックする必要はないので、O（n）にすることはできません。少なくとも私の非常に基本的で弱い理解に。 – bm0r3son
私はあなたもすべてのノードを考慮する必要があると確信しています。正解を常に出すソートアルゴリズムがあったとしますが、要素の1つを見たことがないとします。その要素はブラックボックスなので、リストの最小値または最大値のいずれかを含め、自由に何かを書くことができます。 「ブラックボックス」要素は1つのスポットに入れることができるので、この仮説的アルゴリズムは必ずしも正確に配置することはできません。したがって、我々は矛盾しておりアルゴリズムは存在しない。すべてのソートアルゴリズムはすべての要素を考慮する必要があります。 – phs