Search type | Search syntax |
---|---|
タグ | [タグ] |
完全一致 | "ここの単語" |
作成者 |
user:1234 user:me (あなたの) |
スコア |
score:3 (3+) score:0 (なし) |
回答 |
answers:3 (3+) answers:0 (なし) isaccepted:yes hasaccepted:no inquestion:1234 |
閲覧数 | views:250 |
コード | code:"if (foo != bar)" |
セクション |
title:リンゴ body:"リンゴ オレンジ" |
URL | url:"*.example.com" |
セーブ | in:saves |
状態 |
closed:yes duplicate:no migrated:no wiki:no |
種類 |
is:question is:answer |
除外 |
-[タグ] -リンゴ |
高度な検索の詳細については、ヘルプ ページをご覧ください。 |
3
票
承認済み
計算量のオーダーを実測値から推測する。
正確に推定するのは難しいです。
まず前提として、ランダウの記号を使った時間計算量の表記は漸近的な挙動を考えるのに使うものであり、もし質問者さんの持っている課題が特定の未知の入力に対する時間計算量(実行時間)を推定したいだけなのであれば、漸近的な挙動を求めなくても実測値から未知の実行時間を直接推定できないか考えることができます。
特に、入力が "小さい" ときの実行時間しか測れず、それらのデータを元 …
1
票
最長経路問題とベルマンフォード法について
NP 完全性が関係してくるような「最長経路問題」とは、重みつき有向グラフの最長の単純路(simple path、頂点が重複しない path)を求める問題のことを指してらっしゃるのだと思います。一方ベルマン・フォード法を使うような「最短経路問題」では最短の路を求める問題を解いています。路ではなく単純路を求めることを踏まえると、単に辺の重みを -1 倍するだけでは足りないと分かります。
また、もし最長 …
5
票
承認済み
ビッグオー、ビックシータの計算方法 (関数に再起がある場合、if文がある場合等)
基本的には、ランダウの記法の定義通りに考えることになります。リンクした Wikipedia 記事だと「その他の漸近記法」にまとめられています。
ビッグオーは関数を上からおさえる、ビッグオメガは関数を下からおさえる、ビッグシータは両方からおさえる "気持ち" があり、その直感のもと数学的な定義がなされていると考えてください。
(1)
はい。fnc(n) の実行時間は O(n) です。つまり「こ …
1
票
1
回答
678
閲覧数
ソートに必要な最低計算量は n log n ではないのか?
長さ n の配列をソートするには、最低でもオーダーで n log n の時間計算量が必要だと聞きました。しかし Wikipedia のソートの記事を見ると、バケットソートやバイトニックソートの平均時間計算量は n log n を下回っているように見えます。何故でしょうか?
1
票
承認済み
ソートに必要な最低計算量は n log n ではないのか?
バケットソートやバイトニックソートが逐次の「比較ソート」ではないからです。
比較ソートとは、大雑把に言うと、ランダムアクセスによる読み書きができる配列に対して、操作として要素の比較と読み書きのみが許されている状況下でのソートアルゴリズムのことです。そしてこの比較ソートを逐次に行う場合の平均時間計算量が Ω(n log n) になります。
それ以外の場合、Ω(n log n) を下回ることがあり …
0
票
承認済み
ドット演算子とアロー演算子を用いてベクトルのノルムを求めるアルゴリズムの計算量について
コメント等から察するに、計算量オーダーの見積もり方を定義から確認するのが早道かな、と思いました。O(N) な気がするのに確信が無いとのことですので、確信を持つために時間計算量が O(N) であることを証明してみます。
まずドット演算子を使った方のアルゴリズムについて考えてみます。
while next_address != NULL do
norm <- norm + (*next_a …
2
票
承認済み
量子コンピュータによってソートは速くなりますか?
比較ソートに限定した場合、長さ n の配列に対する量子アルゴリズムの時間計算量は Ω(n log n) になる[1]ので、漸近的には古典アルゴリズムの場合と変わりません。
「比較ソート以外の場合はどうなのか?」「他に制限を課した場合はどうなるのか?」についてはよく知りません。英語版 Wikipedia の "Quantum sort" によると空間が制限されたときに量子の方が有利になる場合がある …
6
票
1
回答
841
閲覧数
量子コンピュータによってソートは速くなりますか?
ランダムアクセスできる配列に対してソートを行うとき、量子アルゴリズムは逐次の古典的アルゴリズムより漸近的に速くなりえますか?
3
票
承認済み
フィボナッチ数列の計算量について
再帰ありの場合のアルゴリズム fibrecursive(n) の時間計算量が O( ((1 + sqrt(5)) / 2)ⁿ ) というのは正しいです。このアルゴリズムだと O(n) にはなりません。たとえば実際に n を大きくしながらプログラムの実行時間を測れば、O(n) じゃなさそうな結果が出ることでしょう。
質問者さんの間違えていそうな点として、まずはどういう計算に対して「時間 1」を割り …