ForHosting KIT · 開発者向けツール

線形探索の平均比較回数計算ツール

この線形探索の比較回数計算ツールは、n個の要素を持つ集合に対象が存在すると分かっている場合に、逐次探索が何回の等価比較を行うかを示します。対象がどの位置にも同じ確率で存在するという標準的な仮定に基づき、期待比較回数と最悪時の比較回数を返します。開発者、学習者、レビュー担当者は、O(n)という表記を、指定した集合サイズで実際に生じる具体的な回数と結び付けて確認できます。

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

無料で実行 API仕様を見る

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

平均値の基礎となる確率モデルを理解する

線形探索は要素を先頭から順番に調べ、対象を見つけた時点で終了します。存在する対象がn個の位置のどこにでも同じ確率で入っているなら、最初の要素を見つけるには1回、2番目なら2回、最後ならn回の比較が必要です。それぞれの費用が生じる確率は1/nです。したがって期待される費用は1からnまでの整数の算術平均であり、(n + 1) / 2に簡約できます。集合の大きさをnとして入力すると、この正確な式を適用します。この仮定は重要です。結果は時間測定、ハードウェア、特定のプログラミング言語に基づく推定値ではありません。位置が一様に分布する成功探索についての決定論的な比較回数です。特定の位置や値がより頻繁に検索される場合は、それぞれの確率で重み付けする必要があります。また、対象が存在しない場合も扱いません。通常の線形探索では、その場合にn個すべてを調べます。

平均比較回数と最悪時の回数を読み取る

平均値は整数になる場合も、0.5を含む場合もあります。たとえば100要素の集合では期待値が50.5回です。この端数は、1回の実行で半分の比較を行うという意味ではありません。対象位置が一様な成功探索を何度も行ったときの長期的な平均です。最悪時はn回です。対象が最後の位置にあると、全要素を確認するまで見つからないためです。要素が1個なら両方とも1回になります。nが増えると平均は集合サイズの半分に近づきますが、最悪時は全サイズのままです。どちらも線形に増えるため、定数が異なっても成功する線形探索は漸近解析でO(n)に分類されます。示した分布に従う処理量の見積もりには平均を、成功する1回の検索に対する厳密な上限には最悪時をお使いください。ループ制御、メモリアクセス、整列、要素内部の比較費用は含みません。

設計と性能の検討に結果を活用する

具体的な比較回数があれば、漸近記法だけの場合よりもアルゴリズムの議論が明確になります。特に集合が小さい、検索頻度が低い、または更新が多い場合、線形探索の期待作業量を別のデータ構造の構築費用と比較できます。ハッシュ表や整列済み索引は検索作業を減らせますが、構築と保守には単純な走査にはない費用がかかります。この計算ツールは、実行時間のベンチマークを装わずに走査側の値を示します。演習問題の確認、表計算モデルの検証、コードレビューの記録、教材用の安定した値の生成にも利用できます。結果には前提条件も添えてください。対象は存在し、各位置は同じ確率で、探索は先頭から始まり最初の一致で終了します。重複があると最初の一致で止まるため、単純なモデルが成立しないことがあります。対象がない場合はn回、アクセスが一様でない場合は位置ごとの確率を用いた加重期待値をお使いください。

活用例

アルゴリズム演習を確認する

指定した集合サイズについて、成功探索の期待比較回数と最大比較回数を確認できます。

反復検索の作業量を見積もる

存在する対象が未整列の集合内に一様に分布するときの期待比較回数を算出できます。

データ構造の選択を説明する

具体的な走査費用を、索引、整列済み配列、ハッシュ表の構築・保守費用と比較できます。

よくある質問

平均比較回数にはどの式を使いますか？

存在する対象が各位置に同じ確率で入る場合、平均は(n + 1) / 2回です。

平均に0.5回が含まれるのはなぜですか？

これは多数の探索に対する期待値であり、1回の探索の回数ではないためです。個々の探索では必ず整数回の比較を行います。

成功する線形探索の最悪時は何回ですか？

対象が最後の位置にあるときが最悪で、n回の比較が必要です。

対象が存在しない場合も計算できますか？

いいえ。このモデルは対象の存在を前提とします。通常の失敗する線形探索はn個すべてを調べます。

結果は実行時間を表しますか？

いいえ。要素の比較回数だけを数えます。実時間は実装、比較自体の費用、ハードウェア、周辺処理にも左右されます。

開発者向け — APIアクセス

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

エンドポイント

POSThttps://api.kit.forhosting.com/dev/linear-search-avg

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

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

curl -X POST https://api.kit.forhosting.com/dev/linear-search-avg \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"n":100}'

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

import os, requests

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

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

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

リクエスト例

{
  "n": 100
}

レスポンス例

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "dev.linear_search_avg",
  "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の完全なドキュメントを見る →