配列のビトニック性（Bitonicity）を計算するC++プログラム

配列のビトニック性（Bitonicity）とは？

配列のビトニック性（Bitonicity）とは、隣り合う要素同士を比較した結果をもとに算出される指標です。配列全体が「増加傾向にあるのか」「減少傾向にあるのか」をひとつの数値で表すことができます。

具体的な定義は以下の通りです。初期値を0とし、現在の要素 arr[i] を直前の要素 arr[i-1] と比較することで、値を更新していきます。

Bitonicity = 0 （初期状態：arr[0]）
i が 1 から n まで繰り返し：
　Bitonicity = Bitonicity + 1 ; もし arr[i] > arr[i-1]
　Bitonicity = Bitonicity - 1 ; もし arr[i] < arr[i-1]
　Bitonicity = Bitonicity     ; もし arr[i] = arr[i-1]

つまり、要素が増加するたびにカウンタが+1され、減少するたびに-1されます。等しい場合は変化しません。ループが終了した時点でのカウンタの値が、その配列のビトニック性となります。

アルゴリズムの考え方

ビトニック性を求めるには、bitonicity という変数を用意し、配列の各要素について「現在の要素」と「直前の要素」の大小関係を比較しながら更新していきます。すべての要素を走査し終えた時点の変数の値が、最終的なビトニック性になります。

例として、配列 {1, 2, 4, 5, 4, 3} の場合を見てみましょう。

• 増加：1→2、2→4、4→5 の3回 → +3
• 減少：5→4、4→3 の2回 → -2
• 結果：3 − 2 ＝ 1

C++による実装例

#include <iostream>
using namespace std;
int main() {
    int arr[] = { 1, 2, 4, 5, 4, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int Bitonicity = 0;
    for (int i = 1; i < n; i++) {
        if (arr[i] > arr[i - 1])
            Bitonicity++;
        else if (arr[i] < arr[i - 1])
            Bitonicity--;
    }
    cout << "Bitonicity = " << Bitonicity;
    return 0;
}

実行結果

Bitonicity = 1

まとめ

このプログラムは、時間計算量 O(n)・空間計算量 O(1) で配列のビトニック性を効率的に求められます。結果が正の値なら増加傾向が支配的、負の値なら減少傾向が支配的であることを示しており、配列の形状を簡潔に把握するのに役立ちます。