56002


今回書いたプログラムの計算量をヒープを構成する要素数`len(a)` _=n_ としてオーダで考えると _O(log2(n))_ という理解でしょうか。

`2**x for x in range(num)`も`for j in range (len(depth_list))`も繰り返し回数は
_log2(n)+1_ なので、オーダ記法だと全体として _O(log2(n))_
に抑えられると考えましたが、計算量を見積もるのにまだ不慣れなため、ご意見を伺いたいです。

該当プログラム

[code]

    import heapq
    import math
    a = [6, 3, 2, 4, 5, 7, 1, 8]
    heapq.heapify(a)
    
    num = int(math.log2(len(a)))
    
    depth_list = []
    for i in range(num+1):
        depth_list.append(i)
    
    print('depth_list')
    print(depth_list)
    
    
    element= [2**x for x in range(num)] + [len(a) - (2**num - 1)]
    print('element')
    print(element)
    
    total = 0
    for j in range (len(depth_list)):
        total += depth_list[j]*element[j]
    
    print('tolal')
    print(total)
    
[/code]


CC BY-SA 4.0
2019-06-21T14:58:39.347
55989
2019-06-22T06:30:55.957
2019-06-22T02:53:02.973
23994
question
python python3 アルゴリズム 計算量
ヒープの深さと各深さにおける要素数から和を求めるプログラムの時間計算量


まず最初に、Big-
O表記では定数倍の違いは無視するので、`O(log2(n))`という書き方はしません。`O(log(n))`か、数学の式に近い書き方で`O(log
n)`ですね。

ループ絡みの計算量は、

`ループの実行回数 ×` **`ループ1回あたりの計算量`**

となります。

「繰り返し回数は _log2(n)+1_ なので、オーダ記法だと全体として _O(log2(n))_ 」が成立するためには、

### 「ループ1回あたりの計算量」が`O(1)`であること

が条件となります。意図せず`O(1)`より計算量の多いメソッド等を使用していないかも注意すべきです。

というわけでループしているところを順番にチェック。

* * *
[code]

    for i in range(num+1):    #<-実行回数: num+1
        depth_list.append(i)  #<-時間計算量: O(1) ... ?
    
[/code]

リスト操作は呼び出し1回が`O(N)`になるものが多数あるので要注意です。`append`の場合でいうと、内部領域が不足したときに、領域を拡張する操作は`O(N)`なんですが、そのような拡張は`1/N`の確率でしか発生しないように調整されているので、平均では`O(1)`と考えて良いです。

`append`ではなく、`insert`を使用すると話が変わってくる場合もありますので、要注意。

* * *
[code]

    element= [2**x for x in range(num)] + [len(a) - (2**num - 1)]
    
[/code]

ご質問中では無視されているようですが、リスト内包表記も入力のシーケンス長`N`に対して`N`回ループします。1回のループ内では`2**x`の計算を行いますが、これは`O(1)`操作と考えて良い(*1)でしょう。よってここも全体では`O(log(n))`ですね。

*1 値により計算量が変化する可能性もあるんですが、上限もあるので無視しておきます。

* * *

で、最後のループ:

[code]

    for j in range (len(depth_list)):
        total += depth_list[j]*element[j] #<- O(1) ... ?
    
[/code]

ループ内の処理では

  * リストの要素参照(`[]`)
  * 数値型の掛け算(`*`)
  * 数値型の累積加算(`+=`)

などが行われていますが、どれも`O(1)`と考えて良いでしょう。よって、ループ全体の計算量は`O(log(n))`ということになります。

* * *

と言うわけでどのループも同じオーダーで処理ができるので、全体としても同じオーダーで

### `O(log(n))`は正解

と言ってしまって良いと思います。

(私的には、ご質問中の`total`って、何を計算しているのかよくわからないのですが…。)

* * *

計算量の評価の際には`O(1)`ではない操作(以前出てきた`sum`,
`sort`など)を正しく評価してやる必要があります。リスト用の関数など呼ぶ場合には特に気をつけないといけません。


CC BY-SA 4.0
2019-06-22T04:08:00.173
56002
2019-06-22T06:30:55.957
2019-06-22T06:30:55.957
13972
13972
55989
answer