すべての質問
3 件の質問
0
票
1
回答
198
閲覧数
ヒープの深さと各深さにおける要素数から和を求めるプログラムの時間計算量
今回書いたプログラムの計算量をヒープを構成する要素数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)) に抑えられると考えましたが、...
3
票
1
回答
4,114
閲覧数
フィボナッチ数列の計算量について
再帰ありとなし(for文)でn番目のフィボナッチ数を求めるプログラムをpython3.6で書いています。
プログラムの時間計算量をオーダ記法で書くために、プログラム上で確認する方法を探しています。
現在は目視で
再帰ありだとO(1+1+n-2)=O(n)
再帰なしだとO(1+1+3*n)=O(n)
と計算量を考えています。
しかし、フィボナッチ数列のアルゴリズムと計算量の参考Webページでは、
...
1
票
1
回答
259
閲覧数
耐久試験を想定したアルゴリズムにおいて計算量を減らす方法
入力で正の整数Nを与え、1からNまで各要素の差が1の配列Aを作成する
1からNまでの間の整数で探索する値をランダムに生成し、探索する値を超えないが最も値が近い配列Aの要素を見つけるプログラムを書いています。
具体的なアルゴリズムの用途には、衝撃吸収材の精度を測るため、高い所から生卵を落として割れない限界の高さを調べる試験を想定しています。
高さは最大でNmで、...