配列 - リストのサイズのチェックは線形ですか?

リストのサイズのチェックは一定時間であるという回答をオンラインでたくさん見ましたが、その理由がわかりません。

私の理解では、リストは連続したメモリ チャンク (配列など) に格納されないということです。つまり、最初にすべての要素を調べなければ、リストのサイズ (最後の要素のインデックス + 1) を取得する方法はありません。

考えはありますか?

これらの回答をいくつか参照していただけますか?確かにその通りですが、文脈を無視すると、サイズをデータの一部として保持することを指しているのかもしれません。構造体。この場合は定数時間です。

2020 年 9 月 4 日 20:47

この質問が Python に関するものである場合は、質問を編集して [linked-list] を削除し、[python] を追加してください。あなたは配列/リストを参照しており、リンクされたリストについては何も参照していないため、おそらく [linked-list] を削除するでしょう。

2020 年 9 月 21 日 20:53

オンラインで、「チェックしてください」という回答をたくさん見ました。リストのサイズは定数時間です。

この誤った考えは、Python 言語の根本的な欠陥に起因している可能性があります。Python では配列はリストと呼ばれます。 Python の人気が高まるにつれて、単語リストは曖昧になってきました。

リンク リストの長さの計算は、長さが個別に保存され、適切に維持されていない限り、O(n) 操作です。

Python の場合のように、サイズが配列とともに保存されている場合、配列のサイズの取得は定数時間で実行されます。そのため、a=[1,2,3]; len(a) は確かに非常に高速です。

ヌル ポインターやヌル バイトなどの終端値を配列でスキャンする必要がある場合、配列の長さの計算は O(n) 操作になる可能性があります。したがって、C の strlen() は、C 文字列 (null で終了する char 配列) のバイト数を計算します。線形時間で動作します。

事前に位置を保持せずにリストの長さを見つける唯一の方法は、リストを反復処理することです。これらはチャンクに保存されないため、最後の要素に到達するまで反復する必要があります。したがって、時間計算量は O(n) です。もちろん、長さを保持する変数を保存し、要素が追加されるたびに値をインクリメントする (要素が削除されるとデクリメントする) 場合は、最初の要素のみが必要になるため、それを反復処理する必要がなく、定数になります。 、または長さが保存されている場所からデータを取得します。おそらく、ルート要素を使用して長さを保持できるため、長さを取得するためにルート要素をループする必要がなくなります。要するに、あなたは正しいのです。定数であると言えるのは、それが事前に保存されている場合です。