Robustness a better measure of algorithm performance
Download
Author
Musselman, Roger D.
Date
2007-09Advisor
Sanchez, Paul J.
Second Reader
Sanchez, Susan M.
Metadata
Show full item recordAbstract
Algorithms are an essential part of Operations Research (OR) methodology. Therefore, the efficiency of the algorithms must be a consideration. However, traditional approaches to assessing algorithm efficiency do not always captured the real-world tradeoffs involved. This thesis explored the use of a new measure of algorithm efficiency, robustness, and contrasted it with the traditional "big-O" analysis. Sorting algorithms were used to illustrate the trade-offs. The use of Dr. Genichi Taguchi's robust design techniques allowed us to take into account the impact of factors which would be uncontrollable in the real world, by measuring how those factors affect the consistency of the results. These factors, which are treated separately by big-O analysis, are incorporated as an integral part of robust analysis. The hypothesis was that robustness is potentially a more useful description of algorithm performance than the more traditional big-O analyses. The results of experimentation supported this hypothesis. Where big-O analysis only considers the average performance, robustness integrates the average performance and the consistency of performance. Most importantly, the robust analysis we performed yielded results that are consistent with actual usage-practitioners prefer quicksort over heap sort, despite the fact that under big-O analysis heap sort dominates quicksort.
Collections
Related items
Showing items related by title, author, creator and subject.
-
Transient localization in shallow water environments with a vertical line array
Tas, Gerard (Monterey, California. Naval Postgraduate School, 2000-06);Several algorithms based on autocorrelation matching of multiple hydrophone elements in a vertical line array have been developed to localize a broadband transient signal. An earlier developed frequency-domain autocorrelation ... -
Distributed autonomous control of multiple spacecraft during close proximity operations
McCamish, Shawn B. (Monterey, California. Naval Postgraduate School, 2007., 2007-12);This research contributes to multiple spacecraft control by developing an autonomous distributed control algorithm for close proximity operations of multiple spacecraft systems, including rendezvous and docking scenarios. ... -
Mission assignment model and simulation tool for different types of unmanned aerial vehicles
Alver, Yücel; Özdoğan, Murat (Monterey, California. Naval Postgraduate School, 2008-09);The use of unmanned aerial vehicles on the battlefield becomes more and more important every day. Parallel to this growing demand, there is a need for robust algorithms to solve the mission assignment problem in an optimum ...