Empirical Scaling Analyser
Zongxu Mu, Holger H. Hoos · 2015
The time complexity of problems and algorithms, i.e., the scaling of the time required for solving a problem instance as a function of instance size, is of key interest in theoretical computer science and practical applications. This paper presents an automated tool -- Empirical Scaling Analyser (ESA) -- that is designed to perform empirical scaling analysis. The methodological approach underlying ESA was introduced by Hoos [1], then applied to analysing a complete TSP solver [2] and later extended and applied to analysing several prominent SAT solvers [3]. ESA is broadly applicable to analysing different kinds of algorithms as long as running time data can be collected on sets of problem instances of various sizes. It is particularly well suited for the analysis of the empirical time complexity of evolutionary algorithms and other heuristic procedures for solving NP-hard problems.