This is my second article on getting started.

preface

The language is just a tool, and the algorithm is the soul of the program. Today we are going to look at the complexity calculations in the algorithm using the Fibonacci column as an example.

Fibonacci sequence

1. Definition:

First we need to know what the Fibonacci sequence is: also known as the Golden ratio sequence, this sequence starts with the third term, each term is equal to the sum of the first two terms.

F[n]=F[n-1]+F[n-2] (n>=2,F[0]=0,F[1]=1)

2. Implementation scheme

Method 1: use recursive scheme to calculate

 public static int fib1(int n) {
        if (n <= 1) return n;
        return fib1(n - 1) + fib1(n - 2);
 }
 
Copy the code

Method 2:

public static int fib2(int n) {
       if (n <= 1) return n;
       int first = 0;
       int second = 1;
       for (int i = 0; i < n - 1; i++) {
           int sum = first + second;
           first = second;
           second = sum;
       }
       return second;
}
Copy the code

3. Execution result

We use the time-stamp method of the System System to record the method time:

When n = 10:

When n = 45:

When n = 49:

According to the execution result, when n is larger, fiB1 takes longer than FIB2.

Analysis of 4.

We see that FIB1 has fewer lines of code and fewer variables than FIB2, but it takes more time. So how do you evaluate an algorithm?

  • Accuracy, readability, robustness.
  • Time complexity Estimates the number of times an application instruction is executed (execution time).
  • Space complexity Estimates the required storage space

Second, time complexity

Definition 1.

Time complexity estimates the number of times a program instruction is executed (execution time).

Big O notation is commonly used. The Big O. The data size N corresponds to the complexity O(N). It’s O(n,j) if you have multiple data sizes. The big O notation is a rough analytical model. It’s an estimate. It helps us understand the performance efficiency of an algorithm in a short time by ignoring constants, coefficients and low prices.

2. Complexity estimation

Increasing complexity:

The name of the expression For example,
Constant of the order O(1) 9
The logarithmic order O(log2n) 4log2n+22
Linear order O(n) 2n+3
Linear logarithmic order O(nlog2n) 3n+4nlog2n+22
Square order O(n2) n2+2n+6
Cubic order O(n3) 3n3 +3n+22
. . .
K to the power stage O(nk) nk
The index order O(2n) 2n

3. Estimation of Fibonacci sequence method

According to what we call the big O notation. We can estimate that the time complexity of FIB1 using the recursive scheme is O(2n) and that of FIB2 is O(n). So fiB2 takes almost no more time as n gets bigger.

Third, space complexity

Definition 1.

Space complexity Estimates the required storage space. As with time complexity, space complexity estimates the amount of space consumed.

O(1) An object space

O(n) n object Spaces

Fourth, algorithm optimization direction

As the equipment is updated, we will adopt more space-for-time schemes to optimize user experience. Factors such as business requirements also need to be considered.

  • As little storage as possible

  • Perform as few steps as possible

  • Space for time, time for space

At the end

Slowly record what you have learned, accumulating little by little, and constantly updating and supplementing, hoping to maintain such a habit. Look forward to your advice and encouragement.