C++で配列内に存在するキーKの出現確率を求める方法

問題概要

サイズ「n」の配列が与えられ、その配列内に指定された要素 k が存在する場合に、その出現確率を求めることが課題です。

配列の要素数と等しい「n」まで配列全体を走査し、指定された要素(キー)「k」を検索します。要素が配列内に存在する場合はその確率を計算して返し、存在しない場合は 0 を出力します。

入力

arr[] = { 1, 2, 3, 4, 5, 6}
K = 5

出力

配列におけるキー 5 の確率 : 0.166

入力

arr[] = { 1,2,3,4,5,6,7 }
K = 8

出力

配列におけるキー 8 の確率 : 0

考え方

上記はサイズ 7 の配列とキー 2 を例とした説明です。この場合、配列は 7 回走査され、キー値 2 が検索されます。2 が見つかるたびに count などの一時変数を 1 ずつ増やし、2 以外の要素であればカウンタを増やさずに次の要素へ進みます。最終的な判定は以下の通りです。

• カウンタが 0 の場合、つまりキーが配列内に存在しないときは、確率は 0 となります。

• カウンタが 0 以外の値である場合は、次の式を使ってキー「k」の確率を計算します。

  確率(k) = 「k」の出現回数の合計 ÷ 配列の全要素数

  「k」の出現回数 = 4

  配列の全要素数 = 7

  キー(k)の確率 = 4 / 7 = 0.57

アルゴリズム

開始
ステップ1→ 配列内のキーの確率を計算する関数を宣言
    float probab_key(int arr[], int size, int key)
      float型の変数 count = 0 を宣言
      ループ: int i = 0 から i < size の間 i++ ずつ繰り返す
      もし arr[i] == key ならば
         count を 1 増やす
      終了
   終了
   return count / size
ステップ2→ main() 内での処理
   int arr[] = { 1, 2, 3, 4, 5, 6} を宣言
   int key = 5 を宣言
   int size = sizeof(arr) / sizeof(arr[0]) を宣言
   probab_key(arr, size, key) を呼び出す
終了

実装例

#include <bits/stdc++.h>
using namespace std;
// 配列内のキーの確率を計算する関数
float probab_key(int arr[], int size, int key){
    float count = 0;
    for (int i = 0; i < size; i++){
        if (arr[i] == key)
            count++;
    }
    return count / size;
}
int main(){
    int arr[] = { 1, 2, 3, 4, 5, 6};
    int key = 5;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout <<"probability of a key "<<key<<" in an array is :"<<probab_key(arr, size, key);
    return 0;
}

出力

上記のコードを実行すると、以下のような結果が出力されます。

probability of a key 5 in an array is :0.166667

計算量について

この手法では配列全体を一度走査するため、時間計算量は O(n)、補助的に使用するメモリは O(1) となります。配列の要素数が大きくなっても線形時間で処理できるため、単純な探索処理として効率的なアプローチです。