Time complexity and space complexity

️ Preface ️
There are two kinds of algorithm efficiency analysis ： The first is time efficiency , The second is spatial efficiency . Time efficiency is called time complexity , And spatial efficiency is called spatial complexity . Time complexity mainly measures the running speed of an algorithm , The space complexity mainly measures the extra space needed by an algorithm , Next, let's take a look at what is called time complexity and space complexity .

Blog home page ：【 Warm the sun like the wind 】
The high-quality goods Java special column 【JavaSE】、【 Prepare for blue bridge 】、【JavaEE The first step 】、【MySQL】、【 data structure 】
Welcome to thumb up Collection Leave a comment Private letters must be answered

This paper is written by 【 Warm the sun like the wind 】 original , First appeared in CSDN

Bloggers will continue to update their learning records and gain , If you have any questions, you can leave a message in the comment area

The source code involved in the blog and the daily practice code of the blogger have been uploaded Code cloud (gitee)、GitHub

---

Time and space complexity of data structures and algorithms

1. Time complexity

1.1 Concept

Definition of time complexity ： In computer science , The time complexity of the algorithm is a mathematical function , It quantitatively describes the running time of the algorithm . The time that an algorithm takes to execute , In theory , It can't be worked out , Only you put your program on the machine and run , To know . But do we need to test every algorithm on the computer ？ It can be tested on the computer , But it's a lot of trouble , That's why we have the time complexity analysis . The time taken by an algorithm is proportional to the number of statements executed , The number of times the basic operations in the algorithm are executed , Time complexity of the algorithm .

1.2 Calculation

Please calculate func1 How many times has the basic operation been performed ？

 void func1(int N){
     
    int count = 0; 
    for (int i = 0; i < N ; i++) {
    
      for (int j = 0; j < N ; j++) {
    
	count++; 
      } 
    }
    for (int k = 0; k < 2 * N ; k++) {
    
      count++; 
    }

    int M = 10; 
    while ((M--) > 0) {
    
      count++; 
    }

    System.out.println(count); 
 }

Func1 Number of basic operations performed ：

• N = 10 F(N) = 130
• N = 100 F(N) = 10210
• N = 1000 F(N) = 1002010

In practice, when we calculate the time complexity , We don't really have to calculate the exact number of execution , And it only takes about the number of times , So here we use Big O The progressive representation of .

1、 With constant 1 Replace all the addition constants in runtime .
2、 In the modified run times function , Only the highest order terms .
3、 If the highest order term exists and is not 1, The constant multiplied by this item is removed . The result is big O rank .

Big use O After the progressive representation of ,Func1 The time complexity of is ：O(N^2)

• N = 10 F(N) = 100
• N = 100 F(N) = 10000
• N = 1000 F(N) = 1000000

Namely Ignore items that have little impact on the results , Concise representation of execution times , And it's Consider the worst case of the algorithm .

Let's take a few examples to practice ：
【 example 1】

void func2(int N) {
     
​	int count = 0; 
​	for (int k = 0; k < 2 * N ; k++) {
    
​		count++; 
​	}
​	int M = 10; 
​	while ((M--) > 0) {
    
​		count++; 
​	}
​	System.out.println(count); 
}

The time complexity is O ( N ) .

【 example 2】

void func3(int N, int M) {
     
	int count = 0; 
	for (int k = 0; k < M; k++) {
     
		count++; 
	}
	for (int k = 0; k < N ; k++) {
     
		count++; 
	}
	System.out.println(count); 
}

The time complexity is O (M+N ).

【 example 3】

void func4(int N) {
     
	int count = 0; 
	for (int k = 0; k < 100; k++) {
     
		count++; 
	}
	System.out.println(count); 
}

The time complexity is O (1 ).

【 example 4】

void bubbleSort(int[] array) {
     
	for (int end = array.length; end > 0; end--) {
     
		boolean sorted = true; 
		for (int i = 1; i < end; i++) {
     
			if (array[i - 1] > array[i]) {
     
				Swap(array, i - 1, i); 
				sorted = false; 
			} 
		}
		if (sorted == true) {
     
			break; 
		} 
	} 
}

The worst-case execution times of the program are n∗(n−1)/2, The time complexity is O (N^2 ).

【 example 5】

int binarySearch(int[] array, int value) {
     
	int begin = 0; 
	int end = array.length - 1; 
	while (begin <= end) {
     
		int mid = begin + ((end-begin) / 2); 
		if (array[mid] < value) 
		begin = mid + 1; 
		else if (array[mid] > value) 
		end = mid - 1; 
		else
			return mid; 
	}
	return -1; 
} 

Binary search procedure , Every cycle , The excluded elements are less than half , We set the execution times of the program to X, The number of elements is n , When the number of remaining elements is 1 Time , The program needs to find it again , Then there is the following equation ：

										n/2^X=1

be X=log 2 n, namely The time complexity is log 2 n.

【 example 6】

Compute factorial recursion factorial Time complexity of ？

long factorial(int N) {
     
	return N < 2 ? N : factorial(N-1) * N; 
}

The time complexity of recursion = The number of recursions * The number of times each recursion is executed

The number of times the program needs to recurse is n Time , So it's The time complexity is O ( N )

【 example 7】

Compute Fibonacci recursion fibonacci Time complexity of ？

int fifibonacci(int N) {
     
	return N < 2 ? N : fifibonacci(N-1)+fifibonacci(N-2); 
}

Times and =1+2^1+ 2^2+ 2^3+…… +2^(n-1)
=2^n-1
The time complexity is O ( 2^N )

2. Spatial complexity

2.1 Concept

Spatial complexity is the complexity of an algorithm in the running process A measure of the amount of storage space temporarily occupied . Space complexity is not how much the program takes up bytes Space , Because it doesn't make much sense either , therefore Spatial complexity is the number of variables . Spatial complexity calculation rules are basically similar to practical complexity , Also use large O Progressive representation .

2.2 Calculation

【 example 1】

void bubbleSort(int[] array) {
     
	for (int end = array.length; end > 0; end--) {
     
		boolean sorted = true; 
		for (int i = 1; i < end; i++) {
     
			if (array[i - 1] > array[i]) {
     
			Swap(array, i - 1, i); 
			sorted = false; 
			} 
		}
		if (sorted == true) {
     
			break; 
		}
	} 
}

The program only opens up constant level memory space , The space complexity is O ( 1 )

【 example 2】

int[] fifibonacci(int n) {
     
	long[] fifibArray = new long[n + 1]; 
	fifibArray[0] = 0; 
	fifibArray[1] = 1; 
	for (int i = 2; i <= n ; i++) {
     
		fifibArray[i] = fifibArray[i - 1] + fifibArray [i - 2]; 
	}
	return fifibArray; 
}

The program opens up a length of n+1 Array variables for , therefore The space complexity is O ( N).

【 example 3】

long factorial(int N) {
     
	return N < 2 ? N : factorial(N-1)*N; 
} 

Every time you recurse, all the data will occupy a space , The spatial complexity of recursion is the number of recursions .

Of the program The space complexity is O（N）.

3. summary

The time complexity of common algorithms can be divided into the following categories ：

• Constant order , Such as O ( 1 )
• Polynomial order , Such as O(n^2), O(n^3)
• Exponential order , Such as recursive implementation of fiboracci sequence O(2^n)
• Logarithmic order , Like binary search O ( l o g 2 n )

Order of size ：
O(1)<O(logN)<O(N)<O(NlogN)<O(NN)<O(2^N)

---

️ Last words ️

Summing up difficulties , hope uu Don't be stingy with your (＾Ｕ＾)ノ~ＹＯ！！ If there is a problem , Welcome comments and corrections in the comment area