ピボット値の特性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/21 15:10 UTC 版)
中央値の中央値をピボット値として採用すると、ピボット値は以下の様な特性を持つ。 n 5 {\displaystyle {\frac {n}{5}}} 個の小配列に分割した時、その小配列のうち半数（ n 5 × 1 2 = n 10 {\displaystyle {\frac {n}{5}}\times {\frac {1}{2}}={\frac {n}{10}}} 個）の小配列では、各小配列の中央値がピボット値（中央値の中央値）以下である。また、各小配列の中には、必ず各中央値以下である要素が3個存在する。よって、その n 10 {\displaystyle {\frac {n}{10}}} 個の各小配列には、ピボット値以下の要素が少なくとも3個以上存在するはずなので、全体としては、 3 n 10 {\displaystyle {\frac {3n}{10}}} 個の要素がピボット値以下である。同様に、もう半数の小配列には、ピボット値以上の要素が少なくとも3個以上存在するはずなので、全体としては、 3 n 10 {\displaystyle {\frac {3n}{10}}} 個の要素がピボット値以上である。 よって、そのピボット値を使用して配列を2分割をした時、その分割点は少なくとも上位30%から70%の間に存在することになるので、次の探索対象となる配列の要素数は、必ず元の配列の要素数の一定の割合（最悪でも3割、最善だと7割）に減少させることができる。 例として、0から99までの100個の乱数列での中央値の中央値を考えると以下のようになる。 0から99までの100個の乱数列での中央値の中央値12 15 11 2 9 5 0 7 3 21 44 40 1 18 20 32 19 35 37 39 13 16 14 8 10 26 6 33 4 27 49 46 52 25 51 34 43 56 72 79 中央値17 23 24 28 29 30 31 36 42 47 50 55 58 60 63 65 66 67 81 83 22 45 38 53 61 41 62 82 54 48 59 57 71 78 64 80 70 76 85 87 96 95 94 86 89 69 68 97 73 92 74 88 99 84 75 90 77 93 98 91 ここで、背景が 赤色：ピボット値（中央値の中央値） 灰色：ピボット値（中央値の中央値）以下の要素 白色：ピボット値（中央値の中央値）以上の要素 である。 また、（5要素ずつの）各小配列の中では昇順で並べ替えて可視化してあるので、3行目が各小配列の中央値のみを抽出した配列になっている（実際には並べ替える必要はなく、可視化の都合である。実際には各小配列の中での中央値さえ計算できればよい）。加えて、小配列自体はその中央値同士を比較して昇順で並べ替えて可視化してあるので、最終的に、赤色のピボット値より左上にある（30個＝元の配列の要素数の3割の）値は、必ずピボット値以下である。また同様に、右下にある値は必ずピボット値以上であることが分かる。
※この「ピボット値の特性」の解説は、「中央値の中央値」の解説の一部です。
「ピボット値の特性」を含む「中央値の中央値」の記事については、「中央値の中央値」の概要を参照ください。
Weblioに収録されているすべての辞書からピボット値の特性を検索する場合は、下記のリンクをクリックしてください。
全ての辞書からピボット値の特性
を検索
- ピボット値の特性のページへのリンク
