私はBig Oを理解しようとしており、簡単なプログラムをステップ実行することが助けになるかもしれないと考えました。
def sum(n):
k = 0
j = 0
while k < n:
k = k + 1
while j < n:
j = j + 1
k = k + j
return k
kとjには最初に値0が割り当てられます。2つのアサインメントをカウントし、最初のwhileループは1回の割り当てをn回実行し、2回目の割り当ては2回の割り当てを実行します。したがって、式は2 + n + 2nになります。
上記の最初の2つの用語式(2とn)は一定であるため、nが大きくなるにつれてnに2を掛ける第3項に比べて重要ではありません。したがって、コードのBig OはO(2n)になります。
私の論理と答えは正しいのですか?前もって感謝します
回答:
回答№1は2あなたの答えは正しいですが、私たちは言っていません O(2n)、しかし に) 代わりに。
何 に) つまり、アルゴリズムの最悪の場合の時間複雑度が最も直線的に増加するということです。 最終的に フォームのある機能によって束縛される a * n
どこで a いくつかの定数です。実際の定数はbig-O表記には関係ありません。
より技術的には、私は言う 最終的に 私たちがあなたのアルゴリズムの制限された振る舞いと呼んでいることについて話しているので、あなたは非常に大きな入力に対してのみ振る舞いを記述していると考えることができます。
あなたのアルゴリズムの例では、 n
成長し、私たちは配慮についてますます心配しています k = 0
そして j = 0
無視されます。
結論として、big-O表記法は、 実行時間が増加する速度実行時間を正確に記述するのではなく、