big-Oが紹介されたクラスは、かなり簡単だと思って欠席しました。それでも、nが非常に小さくなると、先生はO（n）が関数から外れることについて何か言ったようです。私は本のどこにもこれを見つけることができませんでした。誰かが私を教えてもらえますか？O（n）の調査は、それが重要である場合、ソートアルゴリズムのコンテキストで行われました。
ありがとうジーン
編集：それが照らしている助けてくれてありがとう。フォローアップの質問があります。nがO（n）に対して小さすぎる点を理解するための比較的簡単な数学的方法はありますか？
関連する質問
Big O は、関数の実行時間を説明するのではなく、成長だけを説明します。すべての関数には、追加する必要がある一定の係数またはオーバーヘッドがあります。n が低い場合、このオーバーヘッドはアルゴリズムの改善を大幅に小さくする可能性があります。操作ごとに 50 ミリ秒を必要とするが、O(n) を持つアルゴリズムは、n が小さいとパフォーマンスが低下します。操作ごとに 5 ミリ秒を必要とするが、O(n*n) を持つアルゴリズムよりも優れています。
これが、一般に、小さいセットでは大きな O が問題にならない理由です。単純な比較を行うほとんどのオブジェクトでは、10 個のアイテムのクイック ソートはバブル ソートよりも著しく高速ではなく、100 個のアイテムの線形検索はおそらくバイナリ ツリーよりも高速です。
Big-O 表記の背後にある概念は、アルゴリズムの漸近的なパフォーマンスです。N が大きくなるにつれて、Big-O 表記の項が合計時間を支配するようになります。たとえば、O(N^2) アルゴリズムでは、合計時間 T(N) は次のようになります。
T(N) = a * N * N + b * N + c
N が大きくなるほど、b または c の値に関係なく、N^2 の項が支配的になります。
ただし、N が小さい場合は、b と c の項が重要になります。
たとえば、a = 0.001、b = 1,000、c = 1,000,000 の場合。
N ~ T(N) [1 significant figure]
1 1,000,000 (almost all c)
1,000 2,000,000 (50:50 split on b and c)
1,000,000 2,000,000,000 (50:50 split on a and b)
1,000,000,000 1,000,000,000,000,000 (almost all a)
したがって、低次の項を無視すると、低 N でのパフォーマンスは完全に誤って表現されます。高 N では、低次の項は重要ではありません。
出席した講義の数 (N) が非常に少なくなるにつれて、コースの内容が理解しにくくなります。
たぶん、次は「nが非常に小さくなると関数から逸脱するO(n)」の例です。
たとえば、「n の 50 倍プラス n の 2 乗」の時間を必要とする操作を考えてみましょう。
n が大きい場合、「n の 2 乗」項が支配的となるため、演算は「O(n の 2 乗)」と言えます。
ただし、n が小さい場合、「n の 2 乗」の項は無視でき、「n の 50 倍」の項が支配的になります。そのため、n が小さい場合 (およびその場合のみ)、O(n) であると言えます。 .
上記の答えを拡張するために、ビッグオー記法は、関数の最終的な成長またはその制限動作を測定します。
f = O(g) すべての n > N に対してf(n) <= c*g(n)となるような N と定数 c (N の関数である可能性がある) が存在する場合にのみ
f = 10000000*n および g = n^2 としましょう。
f = O(g) ですが、n の値が小さすぎる場合、たとえば 10000000 未満で c = 1 に設定すると、g(n) <= f(n) であることがわかります。
より極端な例を追加すると、複雑さ n^100000 のアルゴリズムと複雑さ 2^(.0000000001n) のアルゴリズムのどちらを扱いますか。合理的な問題サイズの場合、後者の方が適しています。多くの CS が非常に優れているのは、この種の悪用が許されていることですが、ほとんどの自然なアルゴリズムはそれを利用していません。ほとんどの多項式時間アルゴリズムには小さな定数があります (少なくとも少し作業した後)。
幸運を！
大きな話題ではありませんが、完全を期すために、Big_o表記に関連し、理論的なコンピュータサイエンスで一般的に使用され、コンピュータサイエンスの文献で参照されている可能性のある他の表記について説明します。Big-Θ表記、 Big-Ω表記とlittle-o表記。これらは、成長率の単なる他の（そしてより厳密な）説明です。little-o表記はbig-O表記と間違えられがちです。
little-oは、2つの関数f（x）とg（x）の間の関係でもあります。'f（x）が小さい-o of g（x）'と言うことは、f（x）がg（x）よりもはるかに速く成長することを意味します。より数学的な涙では、xが無限大に近づくにつれて、f（x）/ g（x）の限界はゼロであると言われています。
前の回答で述べたように、big-O表記は、アルゴリズムの成長率の上限を表すために使用されます。これは、実際には2つの関数f（x）とg（x）の間の関係です。ここで、xが無限大になると、f（x）= O（g（x））になります。
さまざまな表記法の簡潔でわかりやすい説明については、Big-oウィキペディアのページを参照してください。
定義によれば、
f（n）= Θ（g（n））は、定数c1とc2、およびこれらのすべてのケースが真であるn0が必要となるように、すべての関数f（n）のセットを意味します。
したがって、必要なのは、すべての条件が真になるようなc1、c2、およびn0を選択することだけです。したがって、c1 c2の特定の組み合わせでは、n <n0を選択した場合、バインドが機能することを保証できません。これがあなたの先生が「逸脱」によって意味したことだと思います。