Читать книгу Data Structure and Algorithms Using C++ - Sachi Nandan Mohanty - Страница 13

The complexity of programs can be judged by criteria such as whether it satisfies the original specification task, whether the code is readable. These factors affect the computing time and storage requirement of the program.

Space Complexity

The space complexity of a program is the amount of memory it needs to run to completion. The space needed by a program is the sum of the following components:

 A fixed part that includes space for the code, space for simple variables and fixed size component variables, space for constants, etc.

 A variable part that consists of the space needed by component variables whose size is dependent on the particular problem instance being solved, and the stack space used by recursive procedures.

Time Complexity

The time complexity of a program is the amount of computer time it needs to run to completion. The time complexity is of two types such as

 Compilation time

 Runtime

The amount of time taken by the compiler to compile an algorithm is known as compilation time. During compilation time it does not calculate for the executable statements, it calculates only the declaration statements and checks for any syntax and semantic errors.

The run time depends on the size of an algorithm. If the number of instructions in an algorithm is large, then the run time is also large, and if the number of instructions in an algorithm is small, then the time for executing the program is also small. The runtime is calculated for executable statements and not for declaration statements.

Suppose space is fixed for one algorithm then only run time will be considered for obtaining the complexity of algorithm, these are

 Best case

 Worst case

 Average case

Best Case

Generally, most of the algorithms behave sometimes in best case. In this case, algorithm searches the element for the first time by itself.

For example: In linear search, if it finds the element for the first time by itself, then it behaves as the best case. Best case takes shortest time to execute, as it causes the algorithms to do the least amount of work.

Worst Case

In worst case, we find the element at the end or when searching of elements fails. This could involve comparing the key to each list value for a total of N comparisons.

For example in linear search suppose the element for which algorithm is searching is the last element of array or it is not available in array then algorithm behaves as worst case.

Average Case

Analyzing the average case behavior algorithm is a little bit complex than the best case and worst case. Here, we take the probability with a list of data. Average case of algorithm should be the average number of steps but since data can be at any place, so finding exact behavior of algorithm is difficult. As the volume of data increases, the average case of algorithm behaves like the worst case of algorithm.