これは私の最後のコンプ統計予選でした。私はかなり良いと思った答えを出しました。特定の問題に正解したかどうかではなく、試験で点数を取得するだけです。コミュニティがこれに関するガイダンスを提供してくれることを願っていますが、私は何がテストされているのか、どこに行けばそれについてもっと読むことができ、次の試験の前に練習できるのかという答えにはあまり興味がありません.
一見、時間計算量の問題のように見えますが、マッピング関数とデータの事前並べ替えについて話し始めると、どう処理すればよいかわかりません。では、あなたはどのように答えますか？
ここにあります：
あるドメイン Z から引き出されたアイテムのセット X = {x1, x2, ..., xn} が与えられた場合、あなたのタスクは、Z 内のクエリ アイテム q がセット内で発生するかどうかを見つけることです。簡単にするために、各項目が X で 1 回だけ発生し、Z で任意の 2 つの項目を比較するのに O(l) の時間がかかると仮定できます。
(a) X に q があるかどうかをチェックするアルゴリズムの疑似コードを書いてください。あなたのアルゴリズムの最悪の場合の時間計算量はどれくらいですか?
(b) l が非常に大きい場合 (たとえば、X の各要素が長いビデオの場合)、q \in X をチェックする効率的なアルゴリズムが必要です。k 個の関数 h_i: Z -> {1, 2 へのアクセスが与えられているとします。 , ..., m} は、Z の要素を 1 から m の間の数に一様にマッピングし、k << l および m > n とします。関数 h_1...h_k を使用して q \in X かどうかをチェックするアルゴリズムの擬似コードを記述します。データを前処理することが許可されていることに注意してください。アルゴリズムの最悪の場合の時間の複雑さは?
疑似コードの入力、出力、および仮定について明示してください。