| When Hannibal crossed the Alps into Italy, it was no longer as simple to respond to a Roman naval threat in Spain as it was before crossing the Alps. Had Hannibal known the entire future Roman strategy before crossing the Alps then (assuming appropriate computational ability) he could have computed an optimal strategy to deal with the Rome/Cartago crisis. Classical computational complexity of algorithms deals with the questions as to what computational resources would Hannibal have needed to perform this computation. Competitive analysis of algorithms deals with the question as to whether Hannibal's decisions were reasonable given his partial understanding of Roman strategy.
Decision making can be considered in two different contexts: making decisions with complete information, and making decisions based on partial information. A major reason for the study of algorithms is to try to answer the question "which is the better algorithm". The study of the computational complexity of algorithms is useful for distinguishing the quality of algorithms based on the computational resources used and the quality of the solution they compute. However, the computational complexity of algorithms may be irrelevant or a secondary issue when dealing with algorithms that operate in a state of uncertainty. Competitive analysis of algorithms has been found useful in the study of such algorithms. |
|
|
|
