How to understand the complexity of Java algorithm

This article focuses on "how to understand the complexity of the Java algorithm", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to understand the complexity of the Java algorithm.

Big O symbol

The "big O symbol" is usually used to measure time complexity. What is the big O symbol? We need to look at some mathematical knowledge first: functions and limits.

2.1. Mathematical examples:

00001. Unary quadratic function f (x) = 2x ^ 2 + 2x+2

00002. When x tends to infinity, write it down as x-> ∞.

00003. X-> ∞, f (x) = 2x ^ 2 + 2x+2 = 2x ^ 2 = 2x ^ 2.

Item 3 above, when x is infinite, 2x ^ 2 + 2x+2 is about 2x ^ 2, which can be understood as 2x ^ 2 + 2x ^ 2 = 2x ^ 2 in the limit thought (algorithm analysis). The reasons are as follows:

When Xero5:

2x ^ 2 + 2x+2=62.

2x ^ 2 = 50.

When the Xerox 500:

2x ^ 2 + 2x+2=501002

2x ^ 2 = 250000.

With the above example, when you continue to increase the value of x, or even infinity, the term 2x+2 in the f (x) function can be ignored. So when x-> ∞, (2x ^ 2 + 2x+2) is about (2x ^ 2), or (2x ^ 2 + 2x+2) = (2x ^ 2). And in the limit thought, the coefficient 2 in front of 2x ^ 2 can also be omitted. In other words, when x-> ∞, 2x ^ 2 ~ x ^ 2.

Through the idea of limit, we will function f (x) = 2x ^ 2 + 2x+2, omitting the remaining term as x ^ 2. That is to say, when x-> ∞, f (x) = 2x ^ 2 + 2x ^ 2 = x ^ 2; use the big O symbol to indicate: X-> infinity, f (x) = O (x ^ 2).

2.2, concept

Large O is used to describe the remainder of truncated infinite series, especially the asymptotic series. The large O symbol indicates the asymptotic upper bound of the function. Just like the mathematical example above, the remaining term of the function f (x) = 2x ^ 2 + 2x+2 asymptotic series is x ^ 2, which is marked O (x ^ 2). That is to say, O (x ^ 2) is the asymptotic upper bound of f (x).

Time complexity

Topic: ask for 1, 2, 3, 3 +. The sum of + n. (Gaussian algorithm)

The code of the ● beginner programmer:

... ...

For (int I = 1; I