【O(n)】計算量の評価方法について【O(log n)】

**デフォルトの名無しさん** · 2013/03/21(木) 17:35:37.80

論文を仕上げるときに欠かせない計算量の考察
ランダウ表記というのがあるそうですが
計算量算出の根拠とかコツとかについて語り合いましょう

関連スレ
O（n)のソートアルゴリズムを発見した
http://toro.2ch.net/test/read.cgi/tech/1212217022/

参考
http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7

**デフォルトの名無しさん** · 2015/12/15(火) 18:59:25.97

１

**デフォルトの名無しさん** · 2015/12/15(火) 20:36:32.63

>>59
素早い返信ありがとうございました

**デフォルトの名無しさん** · 2015/12/16(水) 04:41:02.19

そもそも2だとしたら
「この」アルゴリズムの～
と矛盾するので題意が成り立たない
つまり実は国語の問題だったのである

**デフォルトの名無しさん** · 2015/12/20(日) 16:25:19.99

さむすぎ

**デフォルトの名無しさん** · 2016/08/07(日) 17:01:40.20

>>58

**デフォルトの名無しさん** · 2016/08/26(金) 15:22:07.02

開平・開立のアルゴリズムって最速なのdeath？

**デフォルトの名無しさん** · 2017/01/08(日) 21:33:16.56

F(p, n, r) の計算量を教えてください。

n: 整数
p, r: 整数配列（インデックス0からn-1）

F(p, n, r):
if r[n] ≧ 0: return r[n]
if n == 0: q = 0
else: q = -∞, for i = 1 to n: q = max(q, p[i] + F(p, n-i, r))
return r[n] = q

**デフォルトの名無しさん** · 2017/01/08(日) 21:33:49.00

T(n)
=
c1 + c2 * n + T(n-1) + … + T(0)
=
c1 + c2 * n + T(n-1) + c3*(n-1)

と解けばいいんですかね？

**デフォルトの名無しさん** · 2017/01/08(日) 21:34:12.25

T(n) = c1 + c2*n + T(n-1)
T(0) = c3

この漸化式の解を求めればいいんですかね？

**デフォルトの名無しさん** · 2017/01/08(日) 21:34:50.14

T(n)
=
[T(n) - T(n-1)] + [T(n-2) - T(n-3)] + … + [T(1) - T(0)] + T(0)
=
[c1 + c2*n] + [c1 + c2*(n-1)] + … + [c1 + c2*1] + c3
=
c1*n + c2*(1/2)*n*(n+1) + c3
=
Θ(n^2)

**デフォルトの名無しさん** · 2017/01/08(日) 21:35:29.94

以前に解かれている部分問題を解くための再帰は直ちに戻るので、Fは
各部分問題をただ1度だけ解く。この手続きはサイズが0,1,....,nの部分問題
を解く。サイズがnの部分問題を解くために、for文がn回繰り返される。したがって、
Fの再帰呼び出し全体における、このfor文の繰り返し回数は等差数列を形成し、
総繰り返し回数はΘ(n^2)となる。

**デフォルトの名無しさん** · 2017/07/20(木) 19:12:09.58

もうこうういうの教えないんだな

**デフォルトの名無しさん** · 2017/10/11(水) 13:56:46.10

浅野孝夫著『アルゴリズムの基礎とデータ構造』を読んでいます。

「上の挿入ソートの例のように、基本演算回数（比較回数）は入力サイズ n にのみ
依存するとは言えない。そこで、入力サイズ n の入力のうちでアルゴリズムが最も
多くの基本演算を必要とする入力を考えて、それに対する基本演算回数を、本書ではん、
サイズ n の入力に対するアルゴリズムの計算量（time complexity of an algorithm）と
呼ぶ。すなわち、最悪の場合を想定してアルゴリズムの計算量を定めていることになる。
このようにして定められたアルゴリズムの計算量 T はもちろん n にのみ依存する関数で
あるので T(n) と書ける。上の挿入ソートの例では T(n) = n*(n-1)/2 である。」

と書いてあります。

その後、マージソートのところには、

「マージソートの計算量は T(n) = O(n*log(n)) である」

と書いてあります。

T(n) は最悪の場合の計算量ですから、

T(n) = Θ(n*log(n)) が正しいのではないでしょうか？

ちなみに、浅野さんは、この本の最初のほうで O, Ω, Θ を定義しています。

もちろん、 f(n) ∈ Θ(n*log(n)) ⇒ f(n) ∈ O(n*log(n)) ですが。

**デフォルトの名無しさん** · 2017/10/11(水) 13:57:29.93

浅野さんは、挿入ソートの計算量を

O(n^2)

と書いています。

これも

Θ(n^2)

と書くべきですよね。

>>71

に引用したように、

「上の挿入ソートの例では T(n) = n*(n-1)/2」

ですから。

**デフォルトの名無しさん** · 2017/10/11(水) 14:02:04.45

T(n) を最悪の場合の計算量としたとき、

T(n) ∈ O(f(n))

と書くという場合はあるのでしょうか？

T(n) ∈ Θ(f(n))

とかならず書くことになると思うのですが。

**デフォルトの名無しさん** · 2018/03/05(月) 21:18:11.90

アルゴリズムイントロダクションのヒープソートのところに、

「サイズ n のヒープ上の MAX-HEAPIFY の最悪実行時間が Ω(lg n) であることを示せ。」

という問題があります。

最悪実行時間が Θ(lg n) であることはすぐに分かります。
なぜ、 Ω(lg n) であることを示せという問題なのでしょうか？

**デフォルトの名無しさん** · 2018/03/05(月) 21:20:53.28

最悪実行時間や最良実行時間については、 Θ 記法で書くのが自然だと思います。

**デフォルトの名無しさん** · 2018/03/06(火) 01:54:50.88

うぃ

**デフォルトの名無しさん** · 2018/05/23(水) 20:13:51.20

僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法　モニアレフヌノ』

ATFOT

**デフォルトの名無しさん** · 2018/07/05(木) 01:30:31.86

K6W

**デフォルトの名無しさん** · 2018/07/08(日) 12:58:38.88

どんな言語だろうが全部ソートすれば O(n*log(n)) で最小値や最大値を探すのは O(n)

この n と n*log(n) の差を無視できないなら
そもそも n と 100*n の差を無視するのもダメじゃないかと思う

**デフォルトの名無しさん** · 2018/07/08(日) 14:27:51.99

>>79
> この n と n*log(n) の差を無視できないなら

上の両者の比はnがどんどん大きくなれば幾らでも大きくなるが

> そもそも n と 100*n の差を無視するのもダメじゃないかと思う

この両者の比はnがいくら大きくなっても100のまま（100に収束するというべきか）

１行目と２行目とではnをどんどん大きくした時の漸近的挙動が全く違うのよ
その違いを理屈として理解する以前に感覚として納得できないならば、君には計算量に関するセンスが決定的に欠落している

**デフォルトの名無しさん** · 2018/09/30(日) 20:17:50.44

てｓｔ

**デフォルトの名無しさん** · 2019/05/22(水) 12:11:36.06

何に使ってますか？