2005cec-tutorial

An Introduction to TimeComplexity of EvolutionaryAlgorithmsTutorial for CEC’2005(Draft)Jun He and Xin YaoCentre of Excellence for Research in Computational Intelligence and ApplicationsSchool of Computer ScienceThe University of Birmingham– p.1Aim and OutlineAimTo give an intuitive introduction to time complexity ofEAs, rather than a rigorous mathematical proof, whichcan be found in the relative references.To raise questions, rather than answer them.OutlinePart A: short introduction to time complexityPart B: time complexity of EAs and research issuesPart C: selected worksPart D: open questions– p.2A1. Time ComplexityTime complexity is used to measure the efficiency of analgorithm and hardness of a problem.“The time complexity of a problem is the number ofsteps that it takes to solve an instance of the problem,as a function of the size of the input, (usually measuredain bits) using the most efficient algorithm”.“To understand this intuitively, consider the example ofan instance that is bits long that can be solved insteps. In this example we say the problem has a timecomplexity of . Of course, the exact number of stepswill depend on exactly what machine or language isabeing used”.aFrom Wikipedia.– p.3A2. Decision ProblemsSo many different problems, however in theoreticalcomputer science,“Much of complexity theory deals with decisionproblems. A decision problem is a problem where theaanswer is always YES/NO”.“Decision ...