質問: n; i > 0; i -= c) { // some O(1) expressions } ``` と書いてありますが、loopを使用した場合計算量はO(n)ではないのですか?この2つの例の違いがよく理解できません。初歩的な質問で申し訳ありません。
回答: **計算量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)です。