Skip to main content

すべての質問

でタグ付けされた
絞り込み
並べ替え
タグ付けされた
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)) に抑えられると考えましたが、...
user avatar
3
1 回答
4,114 閲覧数

フィボナッチ数列の計算量について

再帰ありとなし(for文)でn番目のフィボナッチ数を求めるプログラムをpython3.6で書いています。 プログラムの時間計算量をオーダ記法で書くために、プログラム上で確認する方法を探しています。 現在は目視で 再帰ありだとO(1+1+n-2)=O(n) 再帰なしだとO(1+1+3*n)=O(n) と計算量を考えています。 しかし、フィボナッチ数列のアルゴリズムと計算量の参考Webページでは、 ...
user avatar
1
1 回答
259 閲覧数

耐久試験を想定したアルゴリズムにおいて計算量を減らす方法

入力で正の整数Nを与え、1からNまで各要素の差が1の配列Aを作成する 1からNまでの間の整数で探索する値をランダムに生成し、探索する値を超えないが最も値が近い配列Aの要素を見つけるプログラムを書いています。 具体的なアルゴリズムの用途には、衝撃吸収材の精度を測るため、高い所から生卵を落として割れない限界の高さを調べる試験を想定しています。 高さは最大でNmで、...
user avatar