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

This article introduces how to analyze the time complexity and space complexity of Java data structure, the content is very detailed, interested friends can refer to, hope to be helpful to you.

Algorithm efficiency

In use, the efficiency of the algorithm is divided into two kinds, one is time efficiency (time complexity), the other is space efficiency (space complexity). Time complexity refers to the speed at which the program runs. Space complexity refers to the extra space required by an algorithm.

Time complexity what is time complexity?

The running time of computing programs can not be calculated by simple time, because different processors have different abilities to process data. So just calculate an approximate number of times, which is the number of times the basic operation in the algorithm is executed. It is expressed by the gradual method of big O

Example: the basic operation of calculating func1 has been performed several times

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);}

The basic execution times of func1 is: F (N) = N ^ 2 + 2n + 10

The method of deducing large O-order

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

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

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

So after using the progressive representation of large O, the time complexity of func1 is O (N ^ 2).

Algorithm situation

Because when we use the algorithm, there will be the best case and the worst case and the average case. We often talk about the time complexity in O (N) where the time complexity is the worst case.

The best case is the minimum number of runs.

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 result here is that O (N) is N because the constant is removed according to the calculation method of time complexity. M is 10 can also be ignored.

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);} 这里的时间复杂度是 O(M+N) 因为 M 和 N 的值是未知的，所以是 O(M+N) 举例三： void func4(int N) { int count = 0; for (int k = 0; k < 100; k++) { count++; } System.out.println(count);} 这个的时间复杂度是 O(1) 因为循环里面是常数，所以根据大 O 渐进法，结果就是 O(1) 计算冒泡排序的时间复杂度public static void bubbleSort(int[] arr){ for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if(arr[j] >

Arr [juni1]) {int tmp = arr [j]; arr [j] = arr [juni1]; arr [juni1] = tmp;}

Because of the particularity of bubble sorting, it may be arranged at once, or it may have to be arranged all the way to the end, so there is a best-case scenario and a worst-case scenario.

Best case: compare once, that is O (N)

Worst-case scenario: all the way to the end, O (N ^ 2)

Calculate the time complexity of binary search int binarySearch (int [] array, int value) {int begin = 0; int end = array.length-1; while (begin value) end = mid-1; else return mid;} return-1;}

Because the binary search is half the search, the search scope is halved after each search, for example, looking for 8 in an ordered array of 1-8, that is, the worst-case scenario. The figure is as follows:

As shown in the figure, it takes log2n-1 to complete a binary search in an array, that is, the time complexity is log2n (that is, the logarithm of log with base 2 n).

Calculate the time complexity of factorial recursion long factorial (int N) {return N

< 2 ? N : factorial(N-1) * N;} 计算递归的时间复杂度：递归的次数 * 每次递归执行的次数。 所以这次递归的时候，基本操作递归了 N 次，所以时间复杂度就是 O(N) 计算斐波那契递归的时间复杂度int fibonacci(int N) { return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);} 假设 N 是 5 我们来展开求

As shown in the figure: each calculation will calculate the next layer, but each time there is less on one side and more on the other. So it can be calculated directly according to the same as each side. As shown below:

So there is a formula that can calculate the number of times each calculation, that is: 2 ^ (n-1), so the result is: 2 ^\ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3. 2 ^ (nmur1) = 2 ^ n + 1, so according to the big O asymptotic method, the result is: 2 ^ n.

So the time complexity of the Fibonacci sequence is: 2 ^ n.

Space complexity

Space complexity measures the amount of extra storage space an algorithm takes up during its operation, because it is not necessary to calculate in bytes, but the number of variables. It is also expressed by the big O progressive method.

Calculate the space complexity of bubble sorting public static void bubbleSort (int [] arr) {for (int I = 0; I)

< arr.length; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if(arr[j] >

Arr [juni1]) {int tmp = arr [j]; arr [j] = arr [juni1]; arr [juni1] = tmp;}

Because the variable of the bubble sort does not change, the extra space is constant, so the space complexity is O (1).

Calculate the space complexity of Fibonacci sequence (non-recursive) int [] fibonacci (int n) {long [] fibArray = new long [n + 1]; 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.