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

Editor to share with you when the java can not use the worst-case assessment algorithm complexity, I believe that most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to know it!

Dynamic array

Dynamic arrays, which correspond to ArrayList in Java, are divided into two cases when inserting elements:

If the array is not full, the element can be placed in the subscript of size.

The array is full and needs to be expanded. Generally, the capacity is expanded to N times and 1.5 times in Java. To expand the capacity, you need to create a new array, copy the original elements into the new array one by one, and then insert new elements.

I'll simply write a piece of code, and you can feel it:

Public class DynamicArray {private int [] array; private int size; public DynamicArray (int capacity) {this.array = new int [capacity]; this.size = 0;} / insert elements, what is the time complexity? Public void add (int element) {/ / determine whether to expand if (size > = array.length) {int newCapacity = array.length + (array.length > > 1); int [] newArray = new int [newCapacity]; for (int I = 0; I < array.length; ionization +) {newArray [I] = array [I] } this.array = newArray;} array [size++] = element;} public int [] getArray () {return array;} public static void main (String [] args) {DynamicArray dynamicArray = new DynamicArray (4); dynamicArray.add (1); dynamicArray.add (2); dynamicArray.add (3); dynamicArray.add (4) DynamicArray.add (5); dynamicArray.add (6); for (int element: dynamicArray.getArray ()) {System.out.println (element);}

So, for dynamic arrays, what is the time complexity of its method of inserting elements?

According to the previous section, in a worst-case scenario, the worst-case scenario is that when the element is inserted, the array is full and needs to be expanded, when you need to create an additional array and have a process of traversing the original array.

Therefore, in the worst case, the time complexity of inserting elements in a dynamic array is O (n).

But does it make sense?

It is obviously unreasonable. When I insert the previous (nmur1) element, its time complexity is O (1), and only when the nth element is inserted, its time complexity is O (n). Therefore, it is obviously unreasonable to evaluate the time complexity of dynamic array insertion elements.

So, what if I spread the time it takes to insert the nth element over all the elements?

In this case, the insertion time of each element only needs to be added 1 to O (2), ignoring the constant term, it is still O (1), which is obviously more reasonable.

This approach is somewhat similar to calculating the average time complexity, but it is not the average time complexity, it has a special name called sharing time complexity.

Sharing the time complexity equally, that is, for the individual cases in a batch of samples, the time spent is spread over all the samples, and a time complexity is calculated.

You can compare it with the average time complexity:

There are no individual cases in the calculation of average time complexity, and all samples are treated equally. Think about the process of linear search.

There is an example in the calculation of sharing time complexity, which is often the worst case. Think about the process of inserting elements in a dynamic array.

Linear search for the nth element is not an exception, and its time cannot be spread equally to all elements.

Strictly speaking, these two concepts are different, and if they cannot be understood, it is not a big problem to be the same. For example, if the average time complexity is calculated here, the result is (1: 1) / n = (2n-1) / n = (2n-1) / 2-1, ignoring constants and lower-order terms, and the final result is O (1).

Okay, so, let's take a look at the extra space complexity of inserting elements into a dynamic array.

Is it the same thing? When the array is not full, the extra space complexity is O (1). When the array is full, the extra space complexity is O (n), which becomes O (1).

Therefore, for the process of inserting elements into a dynamic array, the time complexity and extra space complexity of the dynamic array are both O (1).

Quick sort

We all know that the time complexity of the classic quick sort is O (nlogn), so is its worst time complexity also O (nlogn)?

Let's look at the following array:

This is an ordered array, what if you sort it with a classic quick sort at this time?

We take the rightmost element as Pivot, that is, 12, put less than 12 on its left, and greater than 12 on its right, and find that there is nothing larger than 12, so there is no element on the right. After this step, the position of 12 is fixed.

Then, take the rightmost element on each side of 12 as the axis, and there are no elements on the right side of 12, so you only need to deal with the left side, taking 10 as the axis, putting the smaller one on its left, and the larger one on its right side. It is found that there are no elements on the right side of 10 (12 has been fixed). After this step, the position of 10 is fixed.

Similarly, the last step is here at 1, and the sort is complete.

Let's analyze the complexity of the whole process:

In the first step, you need to traverse (nmur1) elements

In the second step, you need to traverse (nmur2) elements

...

For the last step, you need to traverse 0 elements

In this case, the time complexity is: (nmur1) + (nMuth2) +... + 1 + 0 = (nMul 1) nmax 2 = n ^ 2 / 2-nmax 2, ignoring the constant term and lower order term, its time complexity is O (n ^ 2).

So, for ordered arrays, using classical quick sorting, its time complexity is O (n ^ 2), which is also the worst-case scenario.

However, no one seems to have ever told you that the time complexity of classical quick sorting is O (n ^ 2), but O (nlog2). Why?

That is because the ordered array is an isolated case relative to the classical quick sort. After enumerating an infinite number of samples, the possibility of the ordered array is too small. Therefore, we generally say that the time complexity of the classical quick sort is O (nlogn), rather than using the worst case to evaluate its time complexity.

These are all the contents of the article "when can't you use the worst-case assessment algorithm in java?" Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

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.