What is the efficiency of an algorithm?
An algorithm is then particularly efficient if it requires as few resources as possible, i.e. hardly any computing time and memory, to solve a specified problem. The efficiency of an algorithm can be measured in various ways: as a rule, the runtime efficiency and the storage efficiency are used as the most important key figures. This can be measured particularly well in absolute and relative terms and can therefore also be interpreted and evaluated.
In a concrete implementation of a particular programming language, efficiency can be determined as a function of hardware and the input data. However, it is also possible to create an efficiency evaluation independent of the evaluation variable and the implementation. The Landau notation can be used to determine the efficiency of an algorithm.
On what concept is this efficiency based?
For precise mathematical efficiency analyses, the underlying data and a calculation model are needed. It is clarified which data types exist, how the data is stored and which operations are permitted. Then it is determined what time a certain operation on a defined data type requires. A random access machine with simple but "unlimited" memory is used for this purpose. Efficiency is represented as storage efficiency (storage effort), subjective efficiency (acquisition effort) and runtime efficiency (time effort).
Algorithms can be fully analysed in terms of correctness and efficiency. Sorting, searching and optimising can also be considered. Data structures have different efficiencies in storage and access. Decisive for the quality of an algorithm is above all the consideration of large inputs. For practical use, it must always be considered whether the input is large or rather small. In theory, however, asymptotic behaviour is important.
Efficiency is specified independently of the machine in the number of calculation steps. One can break this down according to the number of comparisons and additions or other arithmetic operations. The number of memory locations can also be specified. Thus, the concept of the efficiency of an algorithm can be considered machine-independent. In theory, a Turing machine is often used that has a tape on which input and output can be recorded. The tape is infinitely long and the individual calculation steps are considered.
