[計算量] タグが付いた質問

タグの使い方はまだ書かれていません。

絞り込み
並べ替え
タグ付けされた
1
1 回答
471 閲覧数

最長経路問題とベルマンフォード法について

非負の重み付き有効グラフに対しての最長経路問題がNP困難である事は存じ上げています。しかし、各辺の重みを-1倍したグラフに対し、ベルマンフォード法を用いて最短経路問題を解けば、必然的に最長経路問題も解けるような気がしたのですが何が問題なのでしょうか。
ガツ刺しマン's user avatar
0
1 回答
199 閲覧数

計算量のオーダーを実測値から推測する。

計算量の話題でクイックソートはO(nlogn)などありますが、あるアルゴリズムが複雑で計算量のオーダーを論理的に出すのが難しいとき、計算時間の実測値(入力のサイズを色々変えて計算時間を計る)からオーダーを推測するような手法はあるでしょうか?
Jogenara's user avatar
  • 632
0
1 回答
167 閲覧数

二分探索木を分割する際の計算量

https://www.geeksforgeeks.org/split-a-bst-into-two-balanced-bsts-based-on-a-value-k/?ref=leftbar-rightbar こちらのコードを用いてBSTを分割する際の計算量は、O(h)(hはツリーの高さ)ということは直感的には理解できるのですが、どうしても具体的に証明する方法がわかりません。...
Avril's user avatar
  • 117
2
2 回答
1,204 閲覧数

計算量O(1)とO(n)

https://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/?ref=lbp 上記のサイトには、計算量O(1)の例では // Here c is a constant for (int i = 1; i <= c; i++) { // some O(1) ...
Avril's user avatar
  • 117
0
1 回答
506 閲覧数

C言語からアセンブリ言語に書き出した時の計算量について

前提と質問内容 (前提)3x3の正方行列の掛け算を行うプログラムをC言語で書き、 compiler explorerというC言語のアセンブラ出力を確認できるページで x86-64 icc 19.0.1とMIPS gcc 5.4のアセンブリ言語に出力しました。 (質問)内側のループにおける代入文とフロー制御の命令回数と、...
user avatar
0
1 回答
191 閲覧数

ヒープの深さと各深さにおける要素数から和を求めるプログラムの時間計算量

今回書いたプログラムの計算量をヒープを構成する要素数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
-1
2 回答
401 閲覧数

ドット演算子とアロー演算子を用いてベクトルのノルムを求めるアルゴリズムの計算量について

ドット演算子とアロー演算子を用いて、ベクトルのノルムを求めるアルゴリズムについて 前の質問で、ドット演算子とアロー演算子の違いについて質問させていただきましたが、それぞれの演算子によってプログラムの計算量はオーダ記法では違いはあるのでしょうか。 オーダー記法で計算量を考えると、n次元のベクトルが全て0以外だった時にn回、normが計算されるのでおしなべるとO(n)という理解で合っていますか。 ...
user avatar
3
1 回答
3,880 閲覧数

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

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

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

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

ベクトルで表せる能力値を持ったキャラクター(個体)たちのうち、上位互換が存在しないものたちを選びたい

たとえば、 RPG のキャラクターは、いろいろな能力値をもっています。(体力・素早さ・etc...) つまりは、それぞれのキャラクター能力は、ベクトルで表せる、と表現できます。 # 例えば、 pandas を用いてキャラクター能力値を表現する chara1 = pd.Series({'power': 1, 'speed': 2, 'magic': 3}) chara2 = pd.Series({...
Yuki Inoue's user avatar
  • 1.7万
6
1 回答
817 閲覧数

量子コンピュータによってソートは速くなりますか?

ランダムアクセスできる配列に対してソートを行うとき、量子アルゴリズムは逐次の古典的アルゴリズムより漸近的に速くなりえますか?
nekketsuuu's user avatar
  • 2.4万
1
1 回答
611 閲覧数

ソートに必要な最低計算量は n log n ではないのか?

長さ n の配列をソートするには、最低でもオーダーで n log n の時間計算量が必要だと聞きました。しかし Wikipedia のソートの記事を見ると、バケットソートやバイトニックソートの平均時間計算量は n log n を下回っているように見えます。何故でしょうか?
nekketsuuu's user avatar
  • 2.4万
3
2 回答
965 閲覧数

ビッグオー、ビックシータの計算方法 (関数に再起がある場合、if文がある場合等)

引数 n が負の整数でなく、アルゴリズムの実行時間 = 代入の数 + 数を加算する数とする場合のビッグオー、ビッグシータの求め方について、 (1) fnc(n){ a=0 // +1回 if nが奇数: for i = 1 to n: // +n回 a += 1; // +n回 return a; } ↑...
ynbenson's user avatar
1
1 回答
183 閲覧数

O(k*N^2)kがNと同じと考えられる場合

O(k*N^2)kがNと同じと考えられる場合O(N^3)のようにまとめることは出来ますか? 例えばNxNの行列とN次元ベクトルの掛け算の場合O(N^2)となりますが N回行った場合O(N^3)のようにまとめてもいいのですか?
user avatar
1
1 回答
279 閲覧数

実験的によって計算量を一般式化

ある計算量がわからないアルゴリズムがあったとします。 そのアルゴリズムをどのように評価したらいいですか。 具体的な例だとstd::list<int>の計算量を実験的に知りたいなどです。 単純に実行時間やメモリ消費量を示すのではなく式として一般化するというところまでです。
user avatar
3
0 回答
720 閲覧数

ウェーブレット変換とフーリエ変換の計算量

離散ウェーブレット変換の計算量はO(N)で、高速フーリエ変換の場合はO(N log N)になるそうですが 離散ウェーブレット変換の式も Σ(シグマ記号:summation)が2つのため二重ループになり O(N^2)になると思うのですが、なぜ、O(N)になるのですか?
user avatar