ForHosting KIT · 開発者向けツール

マージソート比較回数計算：最悪・平均ケース

この計算機は、標準的なトップダウン型マージソートがn個の要素に対して行う要素間比較の回数を見積もります。最悪ケースの正確な回数、一様なランダム順序に対する期待値、再帰的な併合レベル数、基準値としてnと2を底とするnの対数の積を返します。これにより、線形対数的な増加を具体的に確認し、二次的な整列処理との差を把握できます。

● Beta無料・ブラウザ内で実行

無料で実行 API仕様を見る

ご利用方法ウェブAPIメールTelegramアプリ近日

計算対象となる比較

対象は併合中に行われる要素同士の順序比較であり、これは一般的なマージソート解析の中心となる操作です。添字の確認、代入、一時配列への書き込み、再帰呼び出し、メモリ確保、独自比較関数の内部処理は含みません。要素が1個なら比較は不要です。入力が大きい場合、範囲を二分して各部分を整列し、未処理の先頭要素を繰り返し比較します。a個とb個のグループの併合では、最後に残った要素を追加比較なしでコピーできるため、最大回数はaとbの和から1を引いた値です。最悪ケースは、nが2の累乗でない場合も含め、実際の分割木全体でこの規則を合算します。n_log2_nは規模の基準として、比較回数の各項目は実用的な推定値としてご利用ください。

最悪ケースと平均ケースの求め方

最悪ケースの正確な式は、nに2を底とするnの対数の切り上げ値を掛け、そこから2の同値乗を引き、1を加えたものです。部分配列を可能な限り均等に分ける標準的な二分マージソートを表します。平均値は、異なるキーの一様ランダムな順列に対する期待値です。a個とb個の列を併合する期待比較回数は、aとbの和から、aをbプラス1で割った値と、bをaプラス1で割った値を引いて求めます。同じ平衡分割木でこの費用を再帰的に加算し、表示結果だけを小数第6位まで丸めます。各実行の比較回数は整数でも、期待値は小数になり得ます。重複キー、別の同値処理、自然な連続列、挿入ソートへの切替条件などがあると実測値は変わります。

線形対数的な結果の読み方

n_log2_nは特徴的な線形対数スケールを示します。併合レベルが1段増えるたびにn個すべてを処理しますが、レベル数自体は対数的にしか増えません。2つの比率項目は推定比較回数を基準値で割り、nが1より大きいときの近さを示します。これらは説明用の値であり、計算量の証明やハードウェア性能測定ではありません。メモリアクセス、確保方式、比較関数の費用、キャッシュ、実行環境が実時間を左右する場合があります。2の累乗の直前と直後を試すと、境界で再帰の深さが変わる様子を確認できます。また、O記法が定数や低次項を省略しても、特定の入力サイズではそれらが無意味ではないことも分かります。

活用例

高コストな比較処理の計画

大規模な安定ソートの前に、重いレコード比較関数の呼び出し回数を見積もります。

アルゴリズムの増加率の学習

さまざまなサイズで正確な回数とn_log2_nを比較できます。

テスト上限の設定

計測機能付き実装の比較カウンターに最悪ケースの上限を設定します。

よくある質問

ここでいう比較とは何ですか？

整列済みの2列を併合する際の要素間の順序比較です。管理処理やデータ移動は除きます。

平均回数が小数になるのはなぜですか？

1回の実行値ではなく、一様ランダムな全順列に対する期待値だからです。

重複値も推定に含まれますか？

いいえ。平均モデルは異なるキーを仮定しており、重複や同値処理によって回数は変わります。

実行時間のベンチマークですか？

いいえ。メモリ、プロセッサー、実行環境、確保処理、比較遅延はモデル化しません。

どのマージソート方式が対象ですか？

各範囲を可能な限り均等に二分する標準的なトップダウン方式です。

APIリクエストの料金はいくらですか？

各APIリクエストは$0.002です。ブラウザーでも同じ決定論的ロジックを利用できます。

開発者向け — APIアクセス

このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。

エンドポイント

POSThttps://api.kit.forhosting.com/dev/merge-sort-comparisons

Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。

お使いのスタックから呼び出す

curl -X POST https://api.kit.forhosting.com/dev/merge-sort-comparisons \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"n":8}'

const res = await fetch("https://api.kit.forhosting.com/dev/merge-sort-comparisons", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "n": 8
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/dev/merge-sort-comparisons",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "n": 8
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/merge-sort-comparisons", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"n":8}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"n":8}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/merge-sort-comparisons", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "n": 8
}

レスポンス例

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "dev.merge_sort_comparisons",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。

料金

1リクエストあたり$0.002

単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。

エラー

HTTP	コード	意味
`401`	`unauthorized`	APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。
`402`	`insufficient_balance`	残高が不足しています。チャージ後に再度お試しください。
`404`	`unknown_type`	指定されたタスクタイプは存在しません。タイプ名を確認してください。
`429`	`rate_limited`	リクエストが多すぎます。しばらく待ってから再度お試しください。

KITの完全なドキュメントを見る →