地味だけど基礎的なデータ構造が 一番汎用的なんじゃないか？ 連結リストとか二分木とかそういうの 0630デフォルトの名無しさん2017/09/15(金) 11:43:47.38ID:NePdqYQx 隣接行列とか 0631デフォルトの名無しさん2017/09/16(土) 07:20:33.50ID:DwhIrlJj>>629 それは言えてるかもしれない 汎用的=基礎的 0632デフォルトの名無しさん2017/09/16(土) 09:24:14.80ID:pDAu8pHG consセル？ 0633デフォルトの名無しさん2017/09/17(日) 17:09:50.02ID:7slIJ8sy Kleinberg & Tardosの本に以下のような内容の記述があります。 でも、 n > 1 のとき、 H が universal になることは決してないですよね。 u = v のとき、常に、 h(u) = h(v) なので、問題の確率は 1 ですから。
-------------------------------------------------- U を要素数の非常に多い有限集合とする。
H を U から {0, 1, ..., n-1} へのすべての写像の集合のある部分集合とする。
u, v ∈ U に対して、ランダムに選んだ h ∈ H が h(u) = h(v) を満たす確率はたかだか 1/n であるとき、 H は universal であるという。 0634デフォルトの名無しさん2017/09/17(日) 17:30:37.45ID:7slIJ8sy S を #S ≦ n であるような任意の U の部分集合とする。 u を U の任意の要素とする。 X を ランダムな選択 h ∈ H に対して、値 #{s ∈ S | h(s) = h(u)} をとるようなランダム変数とする。
このとき、
E[X] ≦ 1
である。
証明：
s ∈ S に対し、 h(s) = h(u) であるならば、 1 h(s) ≠ h(u) であるならば、 0 となるようなランダム変数を X_s とする。
u ∈ S であるとき、破綻しますよね。 0636デフォルトの名無しさん2017/09/17(日) 17:37:20.77ID:7slIJ8sy Kleinbergはネヴァンリンナ賞を受賞した人だそうですが、大丈夫な人なのでしょうか？ 0637デフォルトの名無しさん2017/09/17(日) 18:52:52.16ID:qJGXQCnw ID:7slIJ8syは馬鹿アスペの松坂君 0638デフォルトの名無しさん2017/09/17(日) 23:18:40.22ID:2kxiy1Rb > u = v のとき、常に、
「上の挿入ソートの例のように、基本演算回数（比較回数）は入力サイズ n にのみ 依存するとは言えない。そこで、入力サイズ n の入力のうちでアルゴリズムが最も 多くの基本演算を必要とする入力を考えて、それに対する基本演算回数を、本書ではん、 サイズ n の入力に対するアルゴリズムの計算量（time complexity of an algorithm）と 呼ぶ。すなわち、最悪の場合を想定してアルゴリズムの計算量を定めていることになる。 このようにして定められたアルゴリズムの計算量 T はもちろん n にのみ依存する関数で あるので T(n) と書ける。上の挿入ソートの例では T(n) = n*(n-1)/2 である。」
ですから。 0655デフォルトの名無しさん2017/10/09(月) 20:59:07.08ID:kKYMaHZG 馬鹿アスペの連投 0656デフォルトの名無しさん2017/10/09(月) 21:39:35.32ID:HQb3QT54 ID:vbK8I5kP くらいの基地外になれば、100連投だって容易い。 0657デフォルトの名無しさん2017/10/15(日) 10:39:26.70ID:Cy7I/MU1 ソートの決定木についてですが、葉の数が「少なくとも」 n! 個あると説明されることが多いですが、 ちょうど n! 個と書かない理由は何ですか？ 0658デフォルトの名無しさん2017/10/15(日) 10:46:56.72ID:Cy7I/MU1 既に順序が決定されているにもかかわらず、さらに無駄な比較をするようなプログラムの ことを想定しているのでしょうか？ 0659デフォルトの名無しさん2017/10/15(日) 10:48:49.83ID:Cy7I/MU1 そうだとすると、決定木のある部分木で、その葉がすべて同じ順序に対応するようなものが 存在することになります。 0660デフォルトの名無しさん2017/10/15(日) 10:49:46.78ID:Cy7I/MU1 ソートの決定木について厳密に論じている本はありますか？ 0661デフォルトの名無しさん2017/10/15(日) 11:09:38.82ID:Cy7I/MU1 This result serves as a guide for us to know, when designing a sorting algorithm, how well we can expect to do. For example, without such a result, one might set out to try to design a compare-based sorting algorithm that uses half as many compares as does mergesort, in the worst case. The lower bound in Proposition I says that such an effort is futile?no such algorithm exists 0662デフォルトの名無しさん2017/10/15(日) 11:10:24.51ID:Cy7I/MU1>>661
「このとき根は葉ではないので左の子 v および右の子 w をもつ。」などと書いていますが、 深さ d > 0 の二分木で左の子もしくは右の子を持たないものも当然存在します。 おかしな解答ですね。
二分木において、深さ d までの葉の総数は 2^d 以下であることを示せ。
d に関する帰納法で証明できる。 d = 0 のときは根は葉になるので明らかに成立する。 d > 0 未満で 成立すると仮定し d のときを考える。このとき根は葉ではないので左の子 v および右の子 w をもつ。 v を根とする部分木の深さ d - 1 までの葉が元々の二分木の深さ d までの葉になるがそのような葉の 総数は帰納法の仮定より、 2^(d-1) 以下である。同様に w を根とする部分木の深さ d - 1 までの葉の 総数も 2^(d-1) 以下であり、したがって、元々の二分木の深さ d までの葉の総数は 2^d 以下であることが 言えた。
この問題文自体もおかしいです。
この問題の結果が本文中で使われていてそこを読めばわかるのですが、問題文の意味は、 「深さ d の二分木の葉の総数は 2^d 以下であることを示せ」です。以下のような解答が模範解答ですね。
深さ d の二分木でその葉の総数が 2^d + 1 個以上であるような二分木が存在すると仮定する。 そのような二分木のうち葉の総数が最多であるような二分木を T とする。 すべての葉の深さが d であるような二分木の葉の総数は明らかに 2^d 個である。 よって T の葉にはその深さが d 未満であるような葉が存在する。この葉に子ノードを持たせれば 深さ d の二分木で葉の総数が T の葉の総数よりも多い二分木を作ることができるがこれは矛盾である。 よって、深さ d の二分木の葉の総数は 2^d 個以下である。 0667デフォルトの名無しさん2017/10/21(土) 16:38:07.00ID:FeyeuQ+N >すべての葉の深さが d であるような二分木の葉の総数は明らかに 2^d 個である。
HolderとかRepository作るとどうしてもシングルトンになっちゃう 誰か助けて 0684デフォルトの名無しさん2017/11/07(火) 08:06:23.75ID:FkpvBRAi シングルトンの何がいけないのかをわかっていれば別に使ってもいいんじゃないか？ と思うんだが 0685デフォルトの名無しさん2017/11/08(水) 03:27:16.05ID:pi2d/ZnM staticでおk 0686デフォルトの名無しさん2017/11/10(金) 09:56:08.91ID:O+5a47Rv 内部ノード数 n の 2色木の Black Height を h であらわすと以下の不等式が成り立つ。
2^(h-1) - 1 ≦ n ≦ 2^(2*h-1) - 1
よって、 h = O(log(n))
とある本に書いてあります。
これっておかしいですよね？
h は n の関数ではありません。内部ノード数から2色木の Black Height は一意的にはきまらないからです。
もちろん、 O(log(n)) の左辺には n の関数が来るきまりです。
ですので、 h = O(log(n)) と書くのはおかしいのではないでしょうか？ 0687デフォルトの名無しさん2017/11/10(金) 12:02:03.17ID:WtBM3Wp4 メッセージキューイングって Commandパターンで実装するで合ってる？ 0688デフォルトの名無しさん2017/11/12(日) 17:56:18.04ID:5J9eZD00>>686 >>2^(h-1) - 1 ≦ n ≦ 2^(2*h-1) - 1 ・・・(1) >>よって、 h = O(log(n)) ・・・(2)
一見すると正しそうに見えるけど、どっちがどうおかしいと？ 0689デフォルトの名無しさん2017/11/12(日) 19:28:20.81ID:2NYvmr0h h が n の関数ではないにもかかわらず
h ∈ O(log(n))
と書いているのがナンセンスです。 0690デフォルトの名無しさん2017/11/12(日) 19:46:50.82ID:wWQbf7ET>>689 nとhの関係は(1)で示されているんじゃね？ 不等式を変形すれば良いのでは？ 0691デフォルトの名無しさん2017/11/12(日) 20:23:32.92ID:2NYvmr0h n から h は一意的に決まりません。
よって、
h は n の関数ではありません。 0692デフォルトの名無しさん2017/11/12(日) 21:38:49.52ID:wkhRVmHI>>691 (1)より一意に決まらなくても計算量は同じでしょ？ 0693デフォルトの名無しさん2017/11/13(月) 18:01:47.14ID:O+WFbO9G ＞もちろん、 O(log(n)) の左辺には n の関数が来るきまりです。 ここの時点でおかしい
