すみません、先程の質問に誤りがありました。そのため、私が望んでいた答えが得られませんでした。
先生は、何かを 2 で割るたびに、実行時間は log n になる可能性が高いと教えてくれました。たとえば、配列を 2 つに分割すると、配列の 1 つをトラバースするたびに、実行時間は log n になります。ただし、LinkedList を使用すると、誤解されやすいケースに遭遇する可能性があります。たとえば、ランタイムを n 未満にするために、先頭または末尾のいずれかから開始して、リストの n 番目の要素を別の要素に設定するアルゴリズムがある場合があります。論理的には、実行時間は log n になると考えるかもしれませんが、そうではありません。何故ですか？そして、それをどのように判断しますか？
ログ n のランタイムを取得するために絶対に分割する必要がありますか? ループの最大実行時間が n/2 の場合、n の実行時間を言うのは論理的に意味がないと思います。
時間の複雑さはアルゴリズムのみに関連し、操作しているデータ構造のサイズには関連しないため、ここでいくつかの概念を少し改良する必要があると思います。
先生は、何かを 2 で割るたびに、実行時間は log n になる可能性が高いと教えてくれました。たとえば、配列を 2 つに分割すると、配列の 1 つをトラバースするたびに、実行時間は log n になります。
さて、次のように配列をトラバースします
for (int i = 0; i < array.size; i++) {
variable = array[i];
}
実行O(n)時間 : このような操作を実行するのに必要な時間は、配列のサイズに比例して変化します。配列に対する二分探索O(log n)のような操作を行う必要がありますが、この概念をすべての配列操作に一般化することはできません。特に、配列を反復処理する必要がある人には一般化できません。
さて、この一文
たとえば、ランタイムを n 未満にするために、先頭または末尾のいずれかから開始して、リストの n 番目の要素を別の要素に設定するアルゴリズムがある場合があります。
大きなOで使用されるnとあなたが「n番目の要素」と呼ぶものは直接関係しているとあなたは考えていると私は信じています。そうではありません。連結リストでは、要素 n に移動する唯一のオプションは、リストの先頭に移動し、探している要素までリンクをたどることです (または、二重連結リストの場合は、先頭または末尾に移動します)探している要素の位置に応じて)、この操作の時間の複雑さは O(n) です。つまり、コレクションの長さに線形に関連しています。