Shulou(Shulou.com)06/01 Report--

This article mainly introduces "how to understand time complexity and space complexity through Java algorithm". In daily operation, I believe many people have doubts about how to understand time complexity and space complexity through Java algorithm. Xiaobian consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts of "how to understand time complexity and space complexity through Java algorithm". Next, please follow the editor to study!

1. Algorithm efficiency

There are two kinds of algorithm efficiency analysis: the first is time efficiency and the second is space efficiency. Time efficiency is called time complexity, while space efficiency is called space complexity. The time complexity mainly measures the running speed of an algorithm, while the space complexity mainly measures the extra space needed by an algorithm.

In the early days of the development of computers, the storage capacity of computers was very small. So I care a lot about space complexity. However, with the rapid development of the computer industry, the storage capacity of computers has reached a very high level. So now we no longer need to pay special attention to the space complexity of an algorithm. Because memory is not as expensive as it used to be, it is often heard that space is sacrificed for time.

Second, time complexity 2.1 the concept of time complexity

In computer science, the time complexity of the algorithm is a function, which quantitatively describes the running time of the algorithm.

The number of times the basic operation in the algorithm is executed is the time complexity of the algorithm. In theory, it can not be calculated, only if you put your program on the machine to run, you can know. But do we need to test every algorithm on the computer? Yes, they can all be tested on the computer, but this is very troublesome, so there is a time complexity analysis method.

The time taken by an algorithm is directly proportional to the number of sentences executed in it.

The number of times the basic operation in the algorithm is executed is the time complexity of the algorithm.

2.2 Asymptotic representation of large O

In practice, when we calculate the time complexity, we do not have to calculate the exact number of execution, but only about the number of execution, so here we use the asymptotic representation of large O.

Big O symbol (Big O notation): a mathematical symbol used to describe the progressive behavior of a function.

(1) derive the large O-order method.

Replace all addition constants in run time with the constant 1. In the modified number of runs function, only the highest order items are retained. If the highest order term exists and is not 1, the constant multiplied by the item is removed. The result is a large O-order.

The code is as follows (example):

Void func (int N) {int count = 0 int count / execute 1 for (int I = 0; I

< N ; i++) {//执行N*N次 for (int j = 0; j < N ; j++) { count++; } } for (int k = 0; k < 2 * N ; k++) {//执行2*N次 count++; } int M = 10;//执行1次 while ((M--) >

0) {/ / execute count++;} System.out.println (count) 10 times;}

So the number of times the func method is executed is 1+N2+2*N+1+10

I see the number of times func is executed, and if we assume N = 100 when our N is very large, then the + 1 and + 10 here can be ignored, because 1002 to 10000, + 1 and + 10 are negligible in front of 10,000, so there is no difference between + 1 and + 10.

This is used to derive the large O-order method mentioned earlier.

Replace all addition constants in run time with the constant 1.

It becomes 1+N2+2*N+1+1.

Let's take a look.

In the modified number of runs function, only the highest order items are retained.

Simplified N2

If the highest order term exists and is not 1, the constant multiplied by the item is removed. The result is a large O-order.

Here our highest order term is 2, but there is no constant in front of it, so there is no need to remove it. If there is a 2 in front of N2, that is, 2N2 will be removed from 2 to N2.

So after using the asymptotic representation of large O, the time complexity of Func is O (N2).

From the above, we will find that the progressive representation of large O removes those items that have little impact on the results, and clearly indicates the number of execution times. Time complexity is a function, so we can only roughly estimate the time complexity of this algorithm.

2.3 three cases of time complexity

In addition, the time complexity of some algorithms has the best, average and worst cases.

(1) worst-case scenario

Worst-case scenario: the maximum number of runs of any input size (upper bound) is O (N)

The N here represents the scale of the problem.

(2) best-case scenario

The minimum number of runs of any input size (lower bound) is O (1).

(3) average situation

The expected number of runs of any input size

Note: the average here is not the average of the best and the worst, but the number of times we expect to run, and sometimes the average may be the same as the best or worst.

In general, the time complexity we talk about is the worst-case scenario of the algorithm.

2.4 examples of common time complexity calculations 2.4.1 examples

Example 1:

Void func2 (int N) {int count = 0 Trachap 1 for (int k = 0; k)

< 2 * N ; k++) { //2*N count++; } int M = 10;//1 while ((M--) >

0) {/ / 10 count++;} System.out.println (count);}

After deducing the large O-order method, 1+2*N+1+10 has a time complexity of O (N).

Example 2:

Void func3 (int N, int M) {int count = 0 for / constant can not be added (int k = 0; k)

< M; k++) {//M count++;}for (int k = 0; k < N ; k++) {//N count++;}System.out.println(count);} 时间复杂度为：O(M+N) 示例3： void func4(int N) {int count = 0;for (int k = 0; k < 100; k++) {//用常数1取代运行时间中的所有加法常数 count++;}System.out.println(count);} 这里的时间复杂度为 O(1),因为传进来的N并没有使用 2.4.2 冒泡排序时间复杂度 示例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;}

Best: O (N)

Worst: O (N2)

Average: O (N)

This is an optimized bubble sort, and the best-case scenario is that the set of data is already ordered, so you only need to go through it once, which is also O (N).

And the worst-case scenario is to traverse the whole array, which is N2.

We said earlier that the average situation is what I expect, and what we expect, of course, is O (N).

2.4.3 time complexity of binary search

We know that time complexity is usually the worst case, and binary search is the worst case only when we look for the next two numbers, so we assume that what we are looking for is the outermost number.

Public static int binarySearch (int [] arr,int x) {int left = 0; int right = arr.length-1; int mid = 0 right / intermediate subscript while (left x) {right = mid-1;} else if (arr [mid])

< x){ left = mid+1; }else{ return mid; } } return -1; } 所以二分查找的时间复杂度为 O(log2N) 2.4.4 递归的时间复杂度 递归的时间复杂度 = 递归的次数*每次递归执行的操作的次数 示例1： long factorial(int N) { return N < 2 ? N : factorial(N-1) * N;} 这里的的递归次数为 N 次，这里没有循环，每次执行的是一个三目操作符相当于1次。所以为 N+1次，时间复杂度就是 O(N)。 示例2： 这是一个递归实现的斐波那契数列 public static int fib(int n){ if(n==1||n==2){ return 1; }else{ return fib(n-1)+fib(n-2); }} 斐波那契数列的递归次数其实就是一个等比数列求和，最后的执行次数为 (2n) - 1,通过通过推导大O阶方法最后的时间复杂度为 O(2N) 时间复杂度只是一个大概的，当数字足够大时这里缺失的部分并不影响我们时间复杂度的计算。 三、空间复杂度3.1 空间复杂度概念 空间复杂度是对一个算法在运行过程中临时(额外)占用存储空间大小的量度 占用存储空间大小的量度 。 空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法 3.2 空间复杂度的计算 (1) 冒泡排序 这个冒泡排序的空间复杂度为 O(1) 为什么呢？因为空间复杂度是为了解决一个问题额外申请了其他变量，这里的array数组并不是额外的它是必须的，但这里的 sorted 是额外申请的，它每循环一次就定一次为什么不是O(N)呢？因为每循环一次这个变量是不是不要了呢？所以来来回回就是这一个变量。 void bubbleSort(int[] array) {for (int end = array.length; end >

0; end--) {boolean sorted = true;// extra variable for (int I = 1; I

< end; i++) { if (array[i - 1] >

Array [I]) {Swap (array, I-1, I); sorted = false;}} if (sorted = = true) {break;}

(2) Fibonacci series

The space complexity here is O (N).

Here, in order to find the code of the Fibonacci sequence of 1 ~ N, an additional array space is applied to solve this problem, and the space size is Number1. Because 1 is a constant, the space complexity of this code is O (N).

Public static long [] fibonacci (int n) {long [] fibArray = new long [n + 1]; / / extra space fibArray [0] = 0; fibArray [1] = 1; for (int I = 2; I

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.