アルゴリズム解析
出典: フリー百科事典『ウィキペディア(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
- ^ ただし、量子コンピュータには当てはまらない。
- ^ は数学的帰納法で証明できる。
- ^ この方法では、上述の方法とは異なり、ループの条件部で消費される定数時間を無視しているが、そのような省略が最終的な結果に影響しないことは自明である。
- ^ なお、この成長オーダーは急速すぎるので、実用には耐えない。
アルゴリズム解析と同じ種類の言葉
固有名詞の分類
- アルゴリズム解析のページへのリンク