今回書いたプログラムの計算量をヒープを構成する要素数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)) に抑えられると考えましたが、計算量を見積もるのにまだ不慣れなため、ご意見を伺いたいです。
該当プログラム
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)
for j in range (len(depth_list)): total += depth_list[j]*element[j]
の部分ですが、depth_list
はつまるところelement
のインデックスですので(かつ、depth_list
とelement
の長さ(要素数)は同じ)、for i, v in enumerate(element): total += i * v
と書くこともできます(depth_list
は不要になります)。Σ(k*(2**k)){k=1〜depth-1} + depth * element[depth]
なので、Σ(k*(2**k)){k:[1, depth-1]}
の部分を予め計算しておく方法もあろうかと思います。例えば depth が 10 までならsums = [0, 2, 10, 34, 98, 258, 642, 1538, 3586, 8194, 18484]
になります。この場合、計算量はO(1)
になります。