私はビッグオーの概念を学び始めたばかりです。私が学んだことは、関数 f が関数 g の別の定数倍以下である場合、f は O(g) であるということです。
ここで、サイズ「n」の文字列が「2n」（入力のサイズの2倍）のアルゴリズムステップをとる例に出くわしました。したがって、彼らはかかった時間は O(2n) であると言いますが、O(2n)=O(n) として、時間の複雑さは O(n) と言って、このステートメントに従います。
私はこれを理解していません。2n は常に n より大きいので、どうすれば 2 の倍数を無視できますか? 2n 以下のものは必ずしも n より小さいとは限りません!
n と 2n を何らかの形で同一視しているということではないでしょうか? 紛らわしいですね。私はこの概念の初心者なので、できるだけ簡単に説明してください。よろしくお願いします ：）
Big-Oおよび関連する表記法は、アルゴリズムの実行方法や測定方法に関係なく、アルゴリズムに最も固有のアルゴリズムパフォーマンスの側面をキャプチャすることを目的としています。
一定の乗数は、測定単位、秒対マイクロ秒対命令対ループ反復に依存します。同じ単位で測定した場合でも、異なるシステムで測定した場合は異なります。同じアルゴリズムは、ある命令セットで20n命令、別の命令セットで30n命令を取る場合があります。1つで0.5nマイクロ秒、別で10nマイクロ秒かかる場合があります。
文献に見られる基本的なアルゴリズムの複雑さの多くは数十年前に計算されたものですが、プロセッサアーキテクチャの大幅な変更、さらにはパフォーマンスの大幅な変更に対しても意味があります。
同様の考慮事項が、起動および同様のオーバーヘッドに適用されます。
Af(n)はO(n)、すべてのに対して、定数Nおよびcが存在する場合ですn>=N, f(n) <= cn。f（n）= 2nの場合、定数はとN=0ですc = 2。最初の定数Nはオーバーヘッドを無視することであり、2番目の定数cは定数乗数を無視することです。
... 2n は常に n より大きいので、どうすれば 2 の倍数を無視できますか? ...
簡単に言えばn、乗数が大きくなると、その重要性が失われます。関数の漸近的nな動作は、大きくなるとどうなるかを表します。
と は同じクラスにあるため、だけO(n)でなく、他の一般的なクラスと比較することも役立つかもしれません。例: どのアルゴリズムも、長期的にはどのアルゴリズムよりも時間がかかります(短期的には、実行時間が逆になることさえあります)。2 つのアルゴリズムがあるとします。1 つは の線形時間複雑度で、もう 1 つはです。二次アルゴリズムは、すべてに対して高速になりますが、すべてに対して遅くなります。O(2n)O(n^2)O(n)100n8n^2n =< 12n > 12
このプロパティ –任意の固定された非負cのd場合、 が見つかるnので、cn < dn^2– 時間の複雑さの階層の一部を構成します。
最初の段落で触れたように、アルゴリズムの実行に必要な時間は、入力サイズの定数倍に比例します。O(n) は O(C*n) と考えることができます。ここで、C は任意の定数乗数です。