アルゴリズム解析

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/13 15:58 UTC 版)

意義

非効率なアルゴリズムを使用したためにシステム性能に重大な影響を与えることがあるため、アルゴリズム解析は実用的な意味でも重要である。

（その時点での計算機のスペックとの相対として）膨大なデータを扱う場合、そのオーダーによっては、非効率なアルゴリズムは役に立たない。非効率なアルゴリズムは、たとえば時間や記憶領域を無駄に浪費する。

一方で、ただ単に「実行時間が重要な用途だから」というだけでアルゴリズムに凝るのは、大抵は単なる無駄である。例えば探索について、配列に全て放り込んで、端から探すだけという単純な実装が、データ数が少ない場合にはそれが最も実行時間が少ない、という場合も多い。実例としてはUnixのディレクトリエントリの扱いは古くはそのような実装であった。ボトルネックになる、あるいは膨大なデータになると、あらかじめ確実にわかっているのでなければ、改良する余裕のある、しかし単純な設計でまずは実装し、計測・測定の後に効率化にとりかからなければならない。

参考文献

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford (2001). Introduction to Algorithms. Chapter 1: Foundations (Second ed.). Cambridge, MA: MIT Press and McGraw-Hill. pp. 3–122. ISBN 0-262-03293-7
Sedgewick, Robert (1998). Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching (3rd ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-31452-6
Knuth, Donald. The Art of Computer Programming. Addison-Wesley
Greene, Daniel A.; Knuth, Donald E. (1982). Mathematics for the Analysis of Algorithms (Second ed.). Birkhäuser. ISBN 3-7643-3102-X
Goldreich, Oded (2010). Computational Complexity: A Conceptual Perspective. Cambridge University Press. ISBN 978-0-521-88473-0

関連項目

脚注

^ Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1974). The design and analysis of computer algorithms. Addison-Wesley Pub. Co. , section 1.3
^ Juraj Hromkovič (2004). Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography. Springer. pp. 177–178. ISBN 978-3-540-14015-3
^ Giorgio Ausiello (1999). Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer. pp. 3–8. ISBN 978-3-540-65431-5
^ Wegener, Ingo (2005), Complexity theory: exploring the limits of efficient algorithms, Berlin, New York: Springer-Verlag, p. 20, ISBN 978-3-540-21045-0
^ Robert Endre Tarjan (1983). Data structures and network algorithms. SIAM. pp. 3–7. ISBN 978-0-89871-187-5
^ Examples of the price of abstraction?, cstheory.stackexchange.com
^ How To Avoid O-Abuse and Bribes, at the blog "Gödel’s Lost Letter and P=NP" by R. J. Lipton, professor of Computer Science at Georgia Tech, recounting idea by Robert Sedgewick
^ ただし、量子コンピュータには当てはまらない。
^ $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ は数学的帰納法で証明できる。
^ この方法では、上述の方法とは異なり、ループの条件部で消費される定数時間を無視しているが、そのような省略が最終的な結果に影響しないことは自明である。
^ なお、この成長オーダーは急速すぎるので、実用には耐えない。

「アルゴリズム解析」の続きの解説一覧

アルゴリズム解析と同じ種類の言葉

解析に関連する言葉	スイング解析統計解析アルゴリズム解析流体解析統語解析 >>学術に関連する言葉
解析に関連する言葉	スイング解析統計解析アルゴリズム解析流体解析統語解析 >>同じ種類の言葉 >>分析に関連する言葉

固有名詞の分類

学問	海洋地質学食品科学アルゴリズム解析人間生態学批判理論 >>固有名詞 >>方式・規則一覧 >>主義・方式一覧 >>学問一覧

>> 「アルゴリズム解析」を含む用語の索引
アルゴリズム解析のページへのリンク

アルゴリズム解析意義