65785


<https://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-
loops/?ref=lbp>  
上記のサイトには、計算量O(1)の例では

[code]

       // Here c is a constant   
       for (int i = 1; i <= c; i++) {  
            // some O(1) expressions
       }
    
[/code]

と書いてあり、O(n)の例では、

[code]

       // Here c is a positive integer constant   
       for (int i = 1; i <= n; i += c) {  
            // some O(1) expressions
       }
    
       for (int i = n; i > 0; i -= c) {
            // some O(1) expressions
       }
    
[/code]

と書いてありますが、loopを使用した場合計算量はO(n)ではないのですか？この2つの例の違いがよく理解できません。初歩的な質問で申し訳ありません。


CC BY-SA 4.0
2020-04-20T09:52:36.823
65783
2020-04-20T10:50:54.643
38330
question
アルゴリズム 計算量
計算量O(1)とO(n)


**計算量O(1)の例** で一番肝心なのは、  
この部分です。

[code]

       // Here c is a constant   
    
[/code]

`c`は定数なのです。どんな値を取っても良いものが「定数」と言われると、理解するのが難しいのですが、この`c`とは別に何らかの変量(変数と言っても良い、計算量の場合はよく`n`が使われる)がある時に「`c`は変量`n`が変化しても何の影響も受けずに一定の値である」と言うことを表しています。

* * *

もう一つ大事なのは、(`n`を変量とした時)O(n)で表すのは「変量`n`が変化した時、計算量が`n`の1乗に比例する」ような計算量を表しています。

`c`として、あなたがとんでもなくでかい数と思う数を1つ選んでください。私としては1億くらいで十分でかいと思えるので、仮に1億としますが、自分の好きなもっとでかい数に置き換えて考えてくれても構いません。

[code]

       for (int i = 1; i <= 100000000; i++) {  
            // some O(1) expressions
       }
    
[/code]

このループの実行時間は、(`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)です。


CC BY-SA 4.0
2020-04-20T10:40:26.513
65785
2020-04-20T10:40:26.513
13972
65783
answer


O(f(x))がそもそもどういう意味かといえば、「nが増えると計算量がどう増えてくの？」です。  
nが登場しない＝計算量は一定で増減しないです。O(1)です。

以下イメージ  
O(1)  
計算量が一定  
O(log(n))  
nが増えると計算量が増えるが、増え方がだんだん緩やかになる  
O(n)  
nが増えると計算量が素直に増える  
O(n*log(n))  
nが増えると計算量がややすごく増える  
O(n^2)  
nが増えると計算量がめっちゃすごく増える。  
計算量の増え方が爆発的に増えるので、プログラムでは避ける。


CC BY-SA 4.0
2020-04-20T10:50:54.643
65786
2020-04-20T10:50:54.643
25396
65783
answer