メソッドがあり、その実行時間を計算したい:
print()
{
node* p1 = sentinel_->next_;
while(p1 != sentinel_)
cout << p1->data_ << “ “;
p1 = p1->next_;
}
cout << endl;
}
ループをn-1回while実行できると仮定した場合。T
(n) = 1 + (n-1) + (n-1) + (n-1) + 1 = 3n - 1.
しかし、「入力サイズ」N に使用する正しい値は何ですか?
3n - 1 >= 0であるT(n)に基づいているので、n >= 1/3
または、while ループは少なくとも 1 回実行できるため、nは単に1以上です。
アルゴリズムの複雑さは、通常、漸近表記法で計算されます。これが意味することは、入力のサイズが変化したときにアルゴリズムがどのように動作するかです。
あなたの例では、「n」は何でもかまいません。n == 2 の場合、while ループは 1 回実行されます。n == 3 の場合、while ループは 2 回実行されます。 「ン」。これは、「n」の値が大きくなると、while ループの実行に時間がかかることを意味します。したがって、アルゴリズムの複雑さは、ループが実行される回数によって直接決定されます。また、ループの実行回数は「n」の値によって決まります。したがって、コードの実行の複雑さは O(n) になります。
最初にリストをトラバースし、各ノード値に 10 を追加するメソッドがあるとします。次に、リストを再度走査して、各ノード値を出力します。このアルゴリズムの実行の複雑さは、O(n) + O(n) = 2 * O(n) になります。定数が無視されるため、これは依然として O(n) ランタイムに相当します。繰り返しますが、これはあくまでも理論上の話です。実際には、リストを 2 回ループしているため、プログラムが遅くなります。
私の説明が明確であることを願っています。専門用語は一切使いませんが、ご理解いただければ幸いです。