algorithm - 簡単な言語でのアルゴリズムの確率分析?

Question

アルゴリズムの確率的分析を簡単な言葉で説明できる人はいますか? Wiki ページには多くの情報が見つかりませんでした。

Answer 1

比較ベースのソート アルゴリズムの予想実行時間を決定するとします。この問題へのアプローチ方法は次のとおりです。

• アルゴリズムへのすべての可能な入力に対する分布を定義する
  • たとえば、すべて N! N 個の異なる数の順序付けの順列は、同じ確率 (1/N!)
• 可能な入力ごとにランタイムを決定する
• すべての可能な入力について、入力の確率と入力の実行時間の積を合計して 、予想される実行時間を計算します。
  • つまり、E[Runtime] = sum _i=1,...,N! { P(i) * ランタイム(i) } = 合計_i=1,...,N! { ランタイム(i) } / N!

たとえば、クイックソート アルゴリズム (単純なピボットの選択) でこれを行うと、クイックソートの予想される実行時間は O(N log N) であるのに対し、最悪の場合の実行時間は O(N ² ) であることがわかります。