jeneshicc https://blog.hatena.ne.jp/jeneshicc/ 落書き、時々落学 https://jeneshicc.hatenadiary.org/ 日記 学問 algorithm Memo 解決 昨日，解法と共に知った問題．メモ． n個の要素が与えられる． また，2つの要素を受け取り，同じか否かを判定する判定機が与えられる． この判定機を用いて n/2よりも多く同じものがあるかを判定したい． 計算時間は判定機の使用回数とする． 例） {A, A, B, C} = False. {A, A, A, B} = Ture. {A, A, A, B, C} = Ture. 判定機は同値性判定を行なうのであって，比較はできない（主に[1]に関係してくる）．(1) O(n log n)の判定アルゴリズムを構成せよ． (2) O(n)の判定アルゴリズムを構成せよ． (3) 「n/3より多く同じものが… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjeneshicc.hatenadiary.org%2Fentry%2F20101129%2F1291060652" title=" 気になっている問題 - 落書き、時々落学" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2010-11-29 04:57:32 rich https://jeneshicc.hatenadiary.org/entry/20101129/1291060652 1.0 100%