Introduction to Algorithms 3rd Editionを読むスレ [無断転載禁止]©2ch.net

**デフォルトの名無しさん** · 2017/09/14(木) 20:06:11.31

Introduction to Algorithms 3rd Editionを読むスレ

**デフォルトの名無しさん** · 2017/09/19(火) 21:52:07.71

>>20

どういうことですか？

**デフォルトの名無しさん** · 2017/10/09(月) 18:38:33.45

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

「上の挿入ソートの例のように、基本演算回数（比較回数）は入力サイズ 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:39:39.42

こちらへどうぞ
http://mevius.2ch.net/test/read.cgi/tech/1363854937/

**デフォルトの名無しさん** · 2018/05/23(水) 21:35:13.59

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

SZ9P6

**デフォルトの名無しさん** · 2018/07/05(木) 00:24:18.40

OTQ