An algorithm is a series of execution steps used to solve a particular problem. Using different algorithms to solve the same problem, the efficiency may vary greatly. In order to evaluate the algorithm, we introduce the concept of “algorithm complexity”.

1. Introduction: Fibonacci Sequence

The Fibonacci sequence is known:And find its general formula.

There are many ways to solve the Fibonacci sequence. Here are only two: recursion and inference.

package com.atangbiji;

public class Main {

	public static void main(String[] args) {
		// Output general F(n)
		System.out.println(fib1(1));
		System.out.println(fib1(2));
		System.out.println(fib1(3));
		System.out.println(fib1(4));
		System.out.println(fib1(5));
		
		System.out.println(fib2(70));
	}
	
	If F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n ≥ 3, n ∈ n *), F(n). */
	

	MAX_VALUE * @param * @return f(n) * */
	
	public static long fib1(int n) {
		if (n < 1 || n > 92)
	        return 0;
		if (n < 3)
			return 1;
		
		return fib1(n - 1) + fib1(n - 2);
	}
	
	MAX_VALUE * @param n * @return f(n) * */
	public static long fib2(int n) {
		if (n < 1 || n > 92)
	        return 0;

		//n: 1 2 3 4 5......
		//F(n): 1 1 2 3 5......
		long first = 1;
		long second = 1;
		for (int i = 3; i <= n; i++) {
			long sum = first + second;
			first = second;
			second = sum;
		}
		returnsecond; }}Copy the code

Through the test, we can find that: when the value of n is large (e.g., n = 60), if the recursive method is used to calculate, the result will be found to be delayed; if the horizontal method is used to calculate, the result can be obtained in seconds. It can be seen that the efficiency of the horizontal method is significantly higher than that of the recursive method.

2. How to evaluate the quality of the algorithm?

• correctness
• readability
• Robustness: Ability to respond to and deal with unreasonable input.
• Time complexity: Estimates the number of times a program instruction is executed (execution time).
• Space complexity: The required storage space is estimated.

Note: In general, we mainly consider the time complexity of the algorithm. (Because the current computer memory is generally relatively large)

3. Time complexity estimation

We can estimate the time complexity by the number of times a program’s instructions are executed. Such as:

(1) function test1

public static void test1(int n) {
	// Total number of executions = 14
	
	// 1 (judgment statement can be ignored)
	if (n > 10) {
		System.out.println("n > 10");
	} else if (n > 5) {
		System.out.println("n > 5");
	} else {
		System.out.println("n <= 5");
	}
	
	// 1 + 4 + 4 + 4
	for (int i = 0; i < 4; i++) {
		System.out.println("test"); }}Copy the code

(2) function test2

public static void test2(int n) {
	// Total number of executions = 1 + 3n
	
	//1 + n + n + n
	for (int i = 0; i < n; i++) {
		System.out.println("test"); }}Copy the code

(3) function test3

public static void test3(int n) {
	// Total number of executions = 48N + 1
	
	// 1 + 2n + n * (1 + 45)
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 15; j++) { // 1 + 15 + 15 + 15
			System.out.println("test"); }}}Copy the code

(4) function test4

public static void test4(int n) {
	// Total number of executions = 3n^2 +3n +1
	
	// 1 + 2n + n * (1 + 3n)
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) { // 1 + n + n + n
			System.out.println("test"); }}}Copy the code

(5) ★ Function test5

public static void test5(int n) {
	// Total executions = log2(n)
	
	/* * n = 2, run once * n = 4, run twice * n = 8, run three times * */
	while ((n = n/2) > 0) { // The speed is reduced
		System.out.println("test"); // Consider only the number of times this sentence is executed}}Copy the code

Function test6

public static void test6(int n) {
	// Total execution times = log5(n)
	while ((n = n/5) > 0) {
		System.out.println("test"); // Consider only the number of times this sentence is executed}}Copy the code

Function test7

public static void test7(int n) {
	// Total number of executions = 3n*log2(n) + 3log2(n) + 1
	
	// 1 + 2 * log2(n) + log2(n) * (1 + 3n)
	/* * n = 2, run once * n = 4, run twice * n = 8, run three times * */
	for (int i = 1; i < n; i += i) { // I = I + I = I * 2
		for (int j = 0; j < n; j++) { // 1 + n + n + n
			System.out.println("test"); }}}Copy the code

Big O notation

To further simplify the calculation of complexity, we generally use the big O notation to describe the time (or space) complexity. It represents the complexity of the algorithm when the data size is N.

Properties of big O notation:

(1) Constants, constant coefficients and low-order terms can be ignored.

• 
• 
• 

(2) Logarithmic order generally omit the base, collectively referred to as.

• 

Note: The big O notation is only a rough analytical model, an estimate. It helps us quickly understand the efficiency of an algorithm.

5. Common complexity

Among them:

• When the data size is small, the curves corresponding to each complexity are shown in the figure below.

  

• When the data scale is large, the curves corresponding to each complexity are shown in the figure below.

  

Therefore, when the data size is relatively large, the complexity isIt’s hard for us to accept.

6. Fibonacci number algorithm complexity analysis

(1) Recursion

public static long fib1(int n) {
	if (n < 1 || n > 92)
        return 0;
	if (n < 3)
		return 1;
	
	return fib1(n - 1) + fib1(n - 2);
}
Copy the code

Assuming that calculationwhenandWe can see that the time of each execution of this function depends mainly on the sum operation. Therefore, the number of times the algorithm function instruction is executed is equivalent to the number of times the function is recursively called.

when, the calling process of this function is shown in the figure below.

So, the number of times this function is called recursivelyThe number of nodes in a binary tree.

That is:.

Therefore, the complexity of the algorithm is.

** Note: ** careful students may find that when, the number of times the function is recursively called is not exactly equal to.

Here’s what needs to be said:Complexity is an estimate, and we care not about specific values, but about orders and trends.So,The trend of exponential growth is indisputable.

(2) Flat push method

public static long fib2(int n) {
	if (n < 1 || n > 92)
        return 0;
	//n: 1 2 3 4 5......
	//F(n): 1 1 2 3 5......
	long first = 1;
	long second = 1;
	for (int i = 3; i <= n; i++) {
		long sum = first + second;
		first = second;
		second = sum;
	}
	return second;
}
Copy the code

Obviously, the time complexity of the flat extrapolation is.

7. Optimization direction of the algorithm

(1) Use as few execution steps (run time) as possible.

(2) Use as little storage as possible.

(3) Depending on the situation, space for time or time for space.

More information on complexity will be covered in the subsequent design and implementation of data structures and algorithms.

(The series of blog posts will continue to be updated after this lecture.)

References: [1] “Love data Structure and Algorithm”, MJ [2] “Data Structure and Algorithm”, Deng Junhui

How do I get the source code?

Follow the wechat public account of “Atang Handwriting” and reply the key words “Data structure and algorithm design and implementation” in the background to obtain the source code of the project.

The original address: www.atangbiji.com/2020/05/12/… The blogger’s latest posts are posted on his personal blog www.atangbiji.com/.