This article has participated in the Denver Nuggets Creators Camp 3 “More Productive writing” track, see details: Digg project | creators Camp 3 ongoing, “write” personal impact.

Why performance analysis?

There are many important things to be aware of, such as user friendliness, modularity, security, maintainability, etc. Why worry about performance?

The simple answer is that we can have all of these things only if we have performance. So performance is like currency, and we can buy all of those things.

In short, performance == scale. Imagine a text editor that can load 1,000 pages, but can spell check one page per minute, or an image editor that takes an hour to rotate an image 90 degrees to the left. If a software feature can’t cope with the scale of the tasks the user needs to perform, it’s as good as dead.

Given two algorithms for a task, how do we figure out which one is better?

A more naive approach is to implement both algorithms, run the two programs on your computer for different inputs, and see which takes less time. This method for analyzing algorithms has many problems.

  1. For some inputs, the first algorithm may outperform the second algorithm. For some inputs, the second performs better.

  2. It is also possible that for some inputs, the first algorithm works better on one machine and the second algorithm works better on other machines for some other inputs.

Asymptotic analysis is a big idea to deal with the above problems in analytical algorithms. In asymptotic analysis, we evaluate the performance of the algorithm based on the input size (we do not measure the actual running time). We calculate how the time (or space) taken up by the algorithm increases with the input size.

For example, let’s consider the search problem in sorting arrays (searching for a given item). One type of search is linear (the order of growth is linear) and the other is binary (the order of growth is logarithmic).

Asymptotic analysis in order to understand how to solve the problem of the above analysis algorithm, suppose we’re on A fast computer to run on linear search, run on A slow computer B binary search, we choose constant value for the two machines, so that it tells us that A given machine accurately within seconds of the time required to perform the search. Assuming that the constant of A is 0.2 and the constant of B is 1000, this means that A is 5,000 times more powerful than B. Fast computers may take less time to input small values of array size N. However, after the input array size reaches a certain value, binary search certainly starts to take less time than linear search, even if the binary search is running on a slow machine. The reason is that binary searches grow in logarithmic order relative to the size of the input, whereas linear searches grow in linear order. Therefore, machine-specific constants can always be ignored after a certain value of size is entered.

Here are some runtimes for this example:

Linear search run time in seconds on A: 0.2 * n

Binary search run time in seconds on B: 1000*log(n)

------------------------------------------------ |n | Running time on A | Running time on B | ------------------------------------------------- |10 | 2 sec | ~ 1 h | -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - | | | | 20 SEC 100 ~ 1.8 h -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - | | | 10 ^ 6 ~ 55.5 h ~ 5.5 h | -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - | | 10 ^ 9 ~ 6.3 years | | ~ 8.3 h -------------------------------------------------Copy the code

Is asymptotic analysis always valid?

Asymptotic analysis is not perfect, but it is the best way to analyze an algorithm. For example, suppose there are two sorting algorithms that take 1000nLogn and 2nLogn time respectively on a machine. The two algorithms are asymptotically the same (the order of growth is nLogn). Therefore, for asymptotic analysis, we cannot tell which is better because we ignore the constants in the asymptotic analysis.

Also, in asymptotic analysis, we always talk about input sizes greater than constant values. It is possible that these large inputs will never be available to your software, and that asymptotically slower algorithms will always perform better in your particular case. As a result, you may end up choosing an algorithm that is asymptotically slow but fast for your software.

Next, algorithm analysis | second (worst, average and best situation)