償却解析
(ならし解析 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/10/10 16:06 UTC 版)
計算機科学における 償却解析（しょうきゃくかいせき、英: amortized analysis）またはならし解析とは、与えられたアルゴリズムの複雑性あるいは計算機資源（特に時間またはメモリ）をどれだけ必要とするかを分析する手法である。償却解析の動機は、一回の実行あたりの最悪実行時間を見ることがあまりにも悲観的であるということである。[1] 与えられたアルゴリズムの一定の動作は著しく計算資源を消費するかもしれないし、他の動作はそれほど消費しないかもしれない。償却分析はアルゴリズムの一連の動作全体にわたってコストが高い、またはそうでもない動作の両方を考慮する。これは、その性能に影響を与える要素(入力の種類、入力の長さなど)の説明を含んでもよい。[2]
- ^ "Lecture 7: Amortized Analysis" (PDF). www.cs.cmu.edu. 2015年3月14日閲覧。
- ^ a b Fiebrink, Rebecca (2007), Amortized Analysis Explained 2011年5月3日閲覧。
- ^ a b c d “Lecture 20: Amortized Analysis”. http://www.cs.cornell.edu/. Cornell University. 2015年3月14日閲覧。
- ^ “CSE332: Data Abstractions”. cs.washington.edu. 2015年3月14日閲覧。
[続きの解説]
- 償却解析のページへのリンク
