私は CLRS の本を読んで勉強していますが、Big-O 分析を学習する最初の例には、配列 A の 2 番目の要素から最後の要素 (26 ページ) までの for ループが含まれていますが、時間のコストは次のようになります。この行は "n" です。
n-1でない理由がわかりません。サイズ 5 (n=5) の配列 A があり、for ループが A[1] から A[4] に移動する場合、それは合計 4 回の繰り返し、つまり n-1 になります。
forループか何かを終了することを確認するために1つの最終チェックを行う必要があるため、実際にはnのコストですか?
これは、彼らが Big-O 分析のすべてを実証しようとしているからです。それは、「大」図に関するものです。通常の数学的説明は次のようなものです: n の値が十分に大きい場合、定数項の加算または減算は、アルゴリズムの複雑さの分析には重要ではありません。
簡単に言えば、配列に米国のような国の市民に関する人口統計情報が含まれている場合、配列のサイズは 3 億要素を超えます。アルゴリズムを比較するとき、アルゴリズムが 2 億 9999 万 9999 回の計算を行った場合と 3 億回の計算を行った場合を気にしますか?
また、丸めと考えることもできます。丸めでは、単純化と明確化のために重要でない小さな数値が切り捨てられます。
Big-O 表記を行う場合、O(n) と O(n - 1) は本質的に同じものです。n が無限大になると、O(n) と O(n - 1) はほぼ同じ速度になります。-1 は無視できます。Big O 分析では通常、パラメーターが無限大に近づくにつれて関数の複雑さが調べられます。
はい、n-1配列の要素を処理する for ループは O(n-1) ですが、O(n) でもあります。正式な定義を考えてみましょう:
f(x) = O(g(x))M正の実数とそのx0よう|f(x)| ≤ M·|g(x)|な実数が存在する場合にのみx > x_0.
M定数とが でx0動作するg(x)=x-1場合 M、x0と も で動作することは明らかですg(x)=x。
のようなBig-O 表記法ではO(g(x))、多項式 g(x) の下位項を無視するのが通例xです。より具体的には、最初の下位項が ( の場合のように) 負号の場合、とg(x)=x-1の新しい値を見つける必要はありません。その項が正符号の場合、第 2 項の係数を掛けると、第 2 項を除いた が得られます。これはwikipediaで詳しく説明されています。Mx0MM
big-O を反復回数の正確なカウントと考えないでください。ループの実行時間は n に比例します。あなたの例では、配列の要素数を 2 倍にすると、ランタイムも約 2 倍になります。それが役立つ場合は、n を大幅に増やすとどうなるかを常に考えてください。
複雑さの分析は、計算が一般的にどのように動作するかを推論するために使用されます。それを行う 1 つの方法は、ますます大きな入力値 (無限大になる) について推論することです。
実際の計算が関数f(n) = 3n + 10であると仮定しましょう
ここで、別の関数g(n) = 5n + 15があるとします。
nは無限大になる傾向があり、2 つの関数を一緒にプロットすると、それらの比率は一定になる傾向があります。したがって、比率が定数になる傾向がある関数は、同様の複雑さであると見なされ、同じ複雑さのクラスに属します。
f(n)はg(n)と同様にO(n)のクラスに属します。編集：明確化。これは、非公式な環境での複雑さについて話すとき、一般的に人々が意味することです。さまざまな種類の漸近線すべてをより深く理解するには、この回答の最後にあるリンクを参照してください。
一方、g(n) = 2^nの場合、それらの比率は一定にならない傾向があるため、同じ複雑度クラスにはなりません。
演習として、 f(n) = log_2(n)とg(n) = log_3(n)の比率がどのように機能するかを考えてみてください。
最後の注意: big-Oh にはより厳密な定義があります。上限とみなされます。したがって、関数がf(n) = 5のような定数の場合、fはO(n)のままです。より深く理解するには、漸近関数のファミリー全体を調べる必要があります。