6
票
Accepted
計算量O(1)とO(n)
計算量O(1)の例 で一番肝心なのは、
この部分です。
// Here c is a constant
cは定数なのです。どんな値を取っても良いものが「定数」と言われると、理解するのが難しいのですが、このcとは別に何らかの変量(変数と言っても良い、計算量の場合はよくnが使われる)がある時に「cは変量nが変化しても何の影響も受けずに一定の値である」と言うことを表しています。
...
5
票
Accepted
ビッグオー、ビックシータの計算方法 (関数に再起がある場合、if文がある場合等)
基本的には、ランダウの記法の定義通りに考えることになります。リンクした Wikipedia 記事だと「その他の漸近記法」にまとめられています。
ビッグオーは関数を上からおさえる、ビッグオメガは関数を下からおさえる、ビッグシータは両方からおさえる "気持ち" があり、その直感のもと数学的な定義がなされていると考えてください。
(1)
はい。fnc(n) の実行時間は O(n) です。つまり「...
3
票
Accepted
計算量のオーダーを実測値から推測する。
正確に推定するのは難しいです。
まず前提として、ランダウの記号を使った時間計算量の表記は漸近的な挙動を考えるのに使うものであり、もし質問者さんの持っている課題が特定の未知の入力に対する時間計算量(実行時間)を推定したいだけなのであれば、漸近的な挙動を求めなくても実測値から未知の実行時間を直接推定できないか考えることができます。
特に、入力が "小さい" ときの実行時間しか測れず、...
3
票
Accepted
C言語からアセンブリ言語に書き出した時の計算量について
(質問)内側のループにおける代入文とフロー制御の命令回数と、プログラム全体の計算複雑度はC言語からアセンブリ言語に変換すると変わるのでしょうか。
一般論として、あるアルゴリズムの実装言語を機械変換(例: C言語→アセンブリ言語へのコンパイル)しても、ビッグ・オー記法の計算複雑度は変化しません。
というよりも「計算複雑度」はアルゴリズムそれ自身から決まりますから、...
3
票
ドット演算子とアロー演算子を用いてベクトルのノルムを求めるアルゴリズムの計算量について
正直言って、「何かBig-O記法をとんでもなく難しいものと勘違いしているんじゃないのか?」と思ってしまいます。
今回の場合、どちらの擬似コードかによらず(別にコメントに合わせて書き換える必要性は全くなかったように思いますが)ループの実行回数はベクトルの次元数nに対してn回だと言う事はわかっているはずです。
編集前を含むどの擬似コードでもループ内で実行される処理はプリミティブなもので、...
3
票
Accepted
フィボナッチ数列の計算量について
再帰ありの場合のアルゴリズム fibrecursive(n) の時間計算量が O( ((1 + sqrt(5)) / 2)ⁿ ) というのは正しいです。このアルゴリズムだと O(n) にはなりません。たとえば実際に n を大きくしながらプログラムの実行時間を測れば、O(n) じゃなさそうな結果が出ることでしょう。
質問者さんの間違えていそうな点として、まずはどういう計算に対して「時間 1」...
3
票
Accepted
耐久試験を想定したアルゴリズムにおいて計算量を減らす方法
目的の値を超えてもいい回数をlife回とすると、life == 1 の時 O(N) ですが、life > 1の時 O(N) より速く解けます
例えば life == 2 の場合
最初に目的の値を超えるまで、sqrt(N) 間隔で調べていき、目的の値を超えたら、最後に超えなかったところから 1 ずつ調べていきます
この時、最初に超えるまでの比較が、O(N / sqrt(N)) ステップかかり、...
2
票
Accepted
量子コンピュータによってソートは速くなりますか?
比較ソートに限定した場合、長さ n の配列に対する量子アルゴリズムの時間計算量は Ω(n log n) になる[1]ので、漸近的には古典アルゴリズムの場合と変わりません。
「比較ソート以外の場合はどうなのか?」「他に制限を課した場合はどうなるのか?」についてはよく知りません。英語版 Wikipedia の "Quantum sort" ...
2
票
Accepted
ヒープの深さと各深さにおける要素数から和を求めるプログラムの時間計算量
まず最初に、Big-O表記では定数倍の違いは無視するので、O(log2(n))という書き方はしません。O(log(n))か、数学の式に近い書き方でO(log n)ですね。
ループ絡みの計算量は、
ループの実行回数 ×ループ1回あたりの計算量
となります。
「繰り返し回数は log2(n)+1 なので、オーダ記法だと全体として O(log2(n))」が成立するためには、
「...
1
票
最長経路問題とベルマンフォード法について
NP 完全性が関係してくるような「最長経路問題」とは、重みつき有向グラフの最長の単純路(simple path、頂点が重複しない path)を求める問題のことを指してらっしゃるのだと思います。一方ベルマン・フォード法を使うような「最短経路問題」では最短の路を求める問題を解いています。路ではなく単純路を求めることを踏まえると、単に辺の重みを -1 倍するだけでは足りないと分かります。
また、...
1
票
Accepted
二分探索木を分割する際の計算量
O(h)(hはツリーの高さ)ではないです。
一旦通りがけ順に要素を列挙した後、その要素を二つの二分探索木に分割してるのでO(N)(Nはツリーのサイズ)です。
一般的な分割の方法では、それぞれの部分木に対して右か左の一方の子を再帰的に分割して、それを定数時間でマージするのでO(h)(hはツリーの高さ)になります。ただしバランスはとれません。
1
票
計算量O(1)とO(n)
O(f(x))がそもそもどういう意味かといえば、「nが増えると計算量がどう増えてくの?」です。
nが登場しない=計算量は一定で増減しないです。O(1)です。
以下イメージ
O(1)
計算量が一定
O(log(n))
nが増えると計算量が増えるが、増え方がだんだん緩やかになる
O(n)
nが増えると計算量が素直に増える
O(n*log(n))
nが増えると計算量がややすごく増える
O(n^...
1
票
Accepted
ソートに必要な最低計算量は n log n ではないのか?
バケットソートやバイトニックソートが逐次の「比較ソート」ではないからです。
比較ソートとは、大雑把に言うと、ランダムアクセスによる読み書きができる配列に対して、操作として要素の比較と読み書きのみが許されている状況下でのソートアルゴリズムのことです。そしてこの比較ソートを逐次に行う場合の平均時間計算量が Ω(n log n) になります。
それ以外の場合、Ω(n log n) ...
Only top scored, non community-wiki answers of a minimum length are eligible