計算量O(1)の例 で一番肝心なのは、
この部分です。
// Here c is a constant
c
は定数なのです。どんな値を取っても良いものが「定数」と言われると、理解するのが難しいのですが、このc
とは別に何らかの変量(変数と言っても良い、計算量の場合はよくn
が使われる)がある時に「c
は変量n
が変化しても何の影響も受けずに一定の値である」と言うことを表しています。
もう一つ大事なのは、(n
を変量とした時)O(n)で表すのは「変量n
が変化した時、計算量がn
の1乗に比例する」ような計算量を表しています。
c
として、あなたがとんでもなくでかい数と思う数を1つ選んでください。私としては1億くらいで十分でかいと思えるので、仮に1億としますが、自分の好きなもっとでかい数に置き換えて考えてくれても構いません。
for (int i = 1; i <= 100000000; i++) {
// some O(1) expressions
}
このループの実行時間は、(n
を変化させた時)「n
の1乗に比例する」でしょうか?そんなことはありません。このループの実行時間にn
が影響を与えることはありません。一定の時間で終わります。だとすれば、このループの時間計算量はO(1)なのです。
もちろん上記の議論は、「変量はn
だけで、c
は定数」と言う共通認識が、読む側と書く側に成立している、と言うのが大前提です。
O(N×M)なんて書き方を見たことがあるでしょうか。こう書いたら「(N
とM
を共に変量とすれば、)計算量はN×M
に比例する、と言うことになります。
したがって、読み手と書き手の間に「c
も変量と考える」と言う共通認識が成り立っていれば、あなたの一つ目の例はO(c)と言うことになります。
実際の問題の場合には、何が変量なのかがはっきりしないまま計算量の話を論じたりすることがありますが、本当はそれは間違いです。
(別のご質問でN
が何を表すのかも書かないまま、O(N)なんて回答に書いてあるのは、本当はいけないこと。)
計算量を表すO(N)と言う記号は、定数倍も無視、低次の項も無視でN
を無限大に持っていったときの極限を考えるため、直感とはちょっとずれてしまうこともよくあります。
O(N)のアルゴリズムの方が、ほとんどの実用的なN
に対してO(1)より速い、なんて場合もいくらでもあったりします。
そこら辺を頭に入れて(変量はn
だけ、c
は定数)、もう一度リンク先の記事を見直して見てください。
n
を2倍、3倍に増やしていった時に、n
に比例して計算量も2倍、3倍に増えていくのであれば、O(n)です。n
の値を何倍に増やしても一定時間で計算を終えるのであればO(1)です。