私はプログラムの実行時間を勉強していて、Big O表記を見つけました。すべての整数に対してn >= x,T(n) <= cf(n)となるように整数xと定数c > 0が存在することを証明することによってT(n)がO(f(n))であることを証明するように求められます。上限と下限の証人を計算する
私が見た例では、xとcの値を「ピッキング」することでこれを証明しています。あなたは値を式に差し込み、それらが正しいかどうかを確認できますが、実際にはxまたはcを計算する方法はありますか？または、少なくとも、それらを選ぶ方法についてのいくつかの大雑把なルールは、無限に値を差し込んでいませんか？
この値は、アルゴリズムTの検査結果です。
for (i=0; i < n; ++i) {
sum += i;
}
i<n、
++iと
sum+=i n回、および
i=0を実行します。たとえば、単純なループを持っている場合。従って
f(n)==n、
c==4（値の正確さのために「1回」から「n回」を上げる）
x==1（
n==0の場合は、
i=0と
i<nを実行するので、式は機能しません）。これにより、O（n）のパフォーマンス（入力数に線形）が得られます。ネストされたループについて
：
for (i=0; i < n; ++i) {
for (j=0; j<n; ++j) {
sum += j;
}
}
計算が与え、f(n)==n^2と、あなたはO（n^2）に類似しています。だから、そこcとxの正確な値を伝えるのないカットのn-乾燥方法はありませんが、ハードの部分はfを考え出すされた時間の中で最も
- あまりにもそれの「最小」（O （n^2）アルゴリズムはO（n^3）アルゴリズムでもありますが、O（n^3）ではなくO（n^2）でそのアルゴリズムを特徴付けたいとします。 fの順序は、nが無限大に近づいたときの成長に基づいています。nが後者よりも大きい場合でも、f(n)=n^3はf(n)=2^nよりも遅くなります。理論的にはxとcの実際の値はnと無関係になることを
注意は、彼らがO(n)表記自体には表示されません。その理由は、無限大に近づきます。これは、（比較的）小さな値の場合、nの場合、命令の数がf(n)よりはるかに大きくないことを意味しません（たとえば、forループ内に1000の命令があります）。
また、O（n）の表記は、あなたが現実の生活（平均ケースのコスト）やデータ構造（償却原価）の全体的な使用法で観察したものよりもはるかに高いかもしれない最悪パフォーマンスを与えます、 例えば。