クイックソートの時間計算量の確率的解析
スポンサーリンク
概要
- 論文の詳細を見る
クイックソートはアルゴリズムにおいてよく知られたソーティングアルゴリズムである.このアルゴリズムは分割統治法に基づいている.ソートすべき配列を,その中のある一要素の値より大きな値の集合と小さな値の集合の二つに分割して,それぞれの部分を独自にソートする.この操作は分割された各部分に対して再度繰り返されるので,このアルゴリズムは再帰的な構造をもつ.クイックソートの平均の時間計算量(平均比較回数)はO(n log n)である.但し,ソートすべきデータによっては性能が極端に悪くなる場合があり,最悪の時間計算量はO(n^2)である.本論文では,まず,クイックソートの時間計算量に基づいた母関数を導入し,これを利用して解析的に時間計算量の平均と分散を求める.そして,この平均と分散を利用して,クイックソートの時間計算量の分布が正規分布で近似できるか,カイ2乗適合度検定を行う.更に,クイックソートの時間計算量の分布を3母数ワイブル分布で近似することにより,時間計算量がある値xを超える確率R(x)を精度良く算出する手法を提案する.最後に,ソーティングアルゴリズムの選択に関する考察を行う.
- 社団法人電子情報通信学会の論文
- 1995-09-25
著者
関連論文
- 表計算ソフトウェアによる路線価評価システムの開発(都市・交通(1))
- コンピュータシステムの障害回復技術(システムの性能評価と信頼性)
- パソコン向け信頼性評価ソフトウエアパッケージツール(信頼性(2))
- キーボードデータ入力操作におけるチェックポイント設定方式とその有効性に関する考察
- チェックポインティング濃度を使用した最適チェックポインティング方策
- キーボード入力操作における主記憶データ書き出し時機に関する考察(信頼性)
- 疎結合マルチプロセッサシステムの保全方策に関する考察(信頼性)
- パーソナルコンピュータの入力データ保全に関する考察(信頼性)
- チェックポインティング濃度を使用した最適チェックポインティング方策
- コンピュ-タシステムにおける再試行の成功回数による保全方策 (新しいフォ-ルトトレランス技術論文小特集)
- マルコフ過程の極限確率の収束時刻の算出
- マルチプロセッサシステムの信頼性・処理性評価
- 処理需要を考慮した計算機システムの信頼性評価
- フォ-ルトトレラントシステムの信頼性評価と比較
- ハイブリッド・データバックアップシステムの経済分析
- 土地価格形成要因の定量データに基づいた固定資産税路線価式評価法(都市・地域(1))
- 比例ハザードモデルに基づいた固定資産税路線価式評価法(金融(2))
- ボルツマンマシンの同定問題としての一考察(非線形最適化)
- 2-E-12 Optimal (T,S)-Policies in a Discrete-Time Opportunity-Based Age Replacement
- 最適な長さに反応する端点停止型細胞をもつ錯視モデル
- 株価指数オプションの価格評価と相関分析
- 確率微分方程式に基づくソフトウェア信頼性評価に関する考察(確立モデル)
- Growth versus Security in Continuous Dynamic Trading Based on Threshold Stopping Rule
- アメリカン・オプションにおける最適行使の理論について(ポートフォリオ)
- オプション売買高の時間推移に関する考察
- 生理学的拘束条件を考慮したシナプス可塑性の数理モデル(最適化理論と数理構造)
- 間欠障害を伴うコンピュータ・システムの最適点検方策
- 1A-3 ベイズの定理を構成したニューラルネットワークによる指数分布の信頼度分布表現(第8回信頼性シンポジウムREAJ)
- ベイズの定理を構成したニューラルネットワークによる指数分布の信頼度分布表現(信頼性)
- 環境の変化に適応できる複製・競合動径基底関数ネットワーク
- 想起機能と探索機能を行うシナジェティック・コンピュータのパラメータ設計法
- ゲーム力学における戦略の確率密度の導出 (決定理論とその関連分野)
- 適者生存型学習則を適用した競合動径基底関数ネットワーク
- シナジェティックコンピュータにおける逆問題の解法
- 一般Lotka-Volterra方程式における逆問題の解法
- パラメータ同定による単純系のポテンシャル形成
- 注視点を考慮した主観的輪郭に反応する低次視覚情報処理モデル
- Dale則を考慮したシナプス可塑性方程式の解析
- 脳梁の構造と機能をモデル化した鏡像ボルツマンマシンにおける1/ƒ揺らぎの出現
- 二つのボルツマンマシンからなる鏡像ボルツマンマシンにおける不可逆過程の解析
- ボルツマンマシンの最適化問題への応用(最適化の数理とその応用)
- エントロピー最大規範によるボルツマンマシンの解析
- エラー修正率を考慮したソフトウェア信頼度成長モデル
- 年齢に依存した費用構造をもつ製品保証の数理モデル(不確実性を含むシステムにおける最適化手法)
- THE SOFTWARE RELEASE GAMES REVISED (Decision Theory in Mathematical Modelling)
- モジュール構造をもつソフトウェアの信頼度成長モデル
- ヒストグラムに基づいた再生関数のノンパラメトリック推定 : 直接リーマンスチルチェス積分法の適用
- EMアルゴリズムに基づいたソフトウェア信頼性モデルの推定
- コスト有効性に基づいた通信ソフトウェアシステムに対する予防保全スケジュールの決定
- Analysis of Hypergeometric Distribution Software Reliability Model (Mathematical Decision Making under Uncertainty)
- 比例ハザードモデルに基づいたソフトウェア製品の信頼性評価
- 一般化された発注-点検モデルについて(信頼性(2))
- ローレンツ曲線上での最適修理費用限界の決定
- ヒストグラムに基づいた再生関数の簡易推定法
- EMアルゴリズムに基づいたソフトウェア信頼性モデルの推定
- コスト有効性に基づいた通信ソフトウェアシステムに対する予防保全スケジュールの決定
- コスト有効性に基づいた通信ソフトウェアシステムに対する予防保全スケジュールの決定(信頼性)
- A Unified Approximation of Optimal Shutdown Schedules Based on a Brownian Motion Process (Mathematical Modeling and Optimization under Uncertainty)
- "政界, 一寸先は闇" : 政権交代はポアソン過程?!
- 動径基底関数ニューラルネットワークを適用した再生関数のノンパラメトリック推定
- ソフトウェア信頼性評価のための無限サーバ待ち行列モデル
- ソフトウエア・マネージメント技法 : プロジェクト管理シミュレーションモデルの構築
- ペナルティコストを考慮したソフトウェアの最適リリース問題に関する考察(信頼性(1))
- 一般化された遅延S字形ソフトウェア信頼度成長モデルとその適合性評価に関する考察
- ソフトウェア開発における資源配分問題(信頼性)
- ソフトウェア信頼度成長モデルに基づくアベイラビリティ評価に関する考察
- 品質評価モデルにもとづく初期流動管理図
- 確率モデルによる釣銭の準備枚数の考察
- ソフトウェア信頼度成長モデルに基づく最適リリース問題(計画数学とその関連分野)
- ソフトウェアエラー発見過程に関する信頼性モデル
- TTT変換を用いた修理限界取換え方策に関する研究(信頼性(3))
- ソフトウェア信頼度成長モデルの適合性評価尺度に関する考察
- Neuronal Firingと再生過程 (神経系と数学的モデル)
- 不完全デバッグを考慮したソフトウェア信頼度成長モデルに関する一考察(信頼性)
- ライフサイクルを考慮したソフトウェアの最適リリース問題(信頼性)
- 2項信頼性モデルによるソフトウェアの信頼性評価(信頼性)
- 行使レベルの時間成長を考慮したアメリカン・コール・オプションの最適停止問題(金融)
- 初期内蔵ソフトウェアエラ-数の事前情報を考慮した2項信頼性モデル
- 代替的評価規範の下での2次記憶媒体に対する最適1/Nバックアップ方策
- ライフサイクルの確率分布とコストの時間的価値を考慮したソフトウェアの最適リリース問題
- フォ-ルトトレラント計算機システムにおける診断方策の考察
- 最適チェックポインティング方策におけるシステム障害の影響について
- 最適チェックポインティング方策におけるシステム障害の影響について(信頼性(1))
- チェックポインティングに起因するシステム障害を考慮した最適チェックポインティング方策
- GMDHネットワークに基づいたソフトウェア出荷スケジュールの生成アルゴリズム
- ニューラルネットワークを用いたソフトウェア最適リリース問題の幾何学的解法
- GMDHネットワークによるソフトウェアのテスト進ちょく度に対する予測評価
- リカレンニューラルネットワークモデルを適用したソフトウェアのテスト進捗度予測手法(第5回研究発表会)
- ソフトウェア最適リリース問題のノンパラメトリック解法(信頼性(2))
- GMDHネットワークによるソフトウェアのテスト進捗度に対する予測評価(信頼性(2))
- AICを用いた改良型GMDHネットワークによるソフトウェアのテスト進捗度予測に関する考察
- ニューラルネットワークを用いたソフトウェアのテスト進捗度予測に関する考察(ファジィ)
- 自動車の揚力特性推定に関する一考察-ニューラルネットワークと多変量解析の併用
- 身障者のポインティング作業に影響する要因の検討
- 代替的評価規範の下でのフロッピーディスクに対する最適1/Nバックアップ方策
- クイックソートの時間計算量の確率的解析
- データフロッピーディスクの最適1/Nバックアップ手続きに対する一般的方法
- 運用段階におけるソフトウェア製品の信頼性評価法 : 加速寿命試験モデルの提案
- データフロッピーディスクの最適1/Nバックアップ手続きに関する一般的方法
- 分散システムの障害回復動作に対する確率的挙動解析 : 一般化確率ペトリネットによるモデル化