📅 preface

As we all know, algorithm and data structure is a necessary course for all computer majors. Algorithm not only reflects a person's logic ability, but also reflects a person's thinking ability. It is not only learning algorithms and data structures, but also a deep understanding of computer science.

In this article, we will start the algorithm and explain the simplest algorithm, linear search method. Ding, start explaining~

After learning this article, you will gain 👇:

• 👏 Understand the basic knowledge of algorithm
• 👏 Understand the basic idea of linear search method
• 👏 Using java language to realize a simple linear search method

I 📝 Basic knowledge of algorithm

1. What is an algorithm

Algorithms are a series of problem-solving, clear, executable computer instructions.

Life is full of algorithms everywhere. For example, asking for directions on the road and saying how to get to Tiananmen Square is an algorithm.

In other words, we want to ask how to solve the univariate quadratic equation? This solution method is also an algorithm.

There may also be a recipe, for example, how to make a dish of fish flavored shredded pork. We can also regard it as an algorithm for its various cooking steps.

2. Five characteristics of the algorithm

The algorithm has five characteristics:

• Finiteness - for an algorithm, it should not be infinite loop, but should be executed in a limited time. The so-called limited time does not mean that this time is very short. As long as it is a certain time, it is limited.
• Certainty - the so-called certainty means that there will be no ambiguity. For example, we now have to face a piece of data, which describes the test scores of all students in a class in different subjects. One of our students may get the highest score when designing an algorithm. But at this time, we don't know which subject has the highest score. At this time, the program will produce ambiguity. Therefore, when designing the algorithm, we should clarify its specific instructions.
• Feasibility - every step in the algorithm should be feasible. For example: suppose there is an algorithm, which explicitly takes out the maximum prime number. But in fact, there are infinite prime numbers, and it is impossible to get the largest. Therefore, this algorithm is not feasible.
• Input - for an algorithm, it must have objects that it needs to operate, so these objects it operates are the input of the algorithm.
• Output - after an algorithm is executed, there will always be a specific response result, and this result is its output value.

II 📈 Linear search method

1. Illustrate with examples

Linear search method can be said to be the simplest algorithm. What is it? for instance 🌰

Suppose there is a stack of papers, we should find our own one in this stack of papers. Then the linear search method will follow the following steps:

• Sheet 1: no
• Sheet 2: No
• Sheet 3: No
• ......
• Sheet 5: Yes! eureka!

As you can see, the linear search method is linear. Search one by one in order.

2. Implementation of linear search method

Suppose there is a set of arrays, we need to find the index of a specific value in the array. How to find it by using the linear search method? First, we create a new java project and a new java class named LinearSearch under the src folder of the project. The specific codes are as follows:

public class LinearSearch {
    // data is an array, and target is the target we want to find
    // In parentheses are function declarations
    public int search(int[] data, int target) {

        // Linear search logic
        for (int i = 0; i < data.length; i++) {
            if (data[i] == target)
                return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] data = {24, 45, 67, 12, 465, 78, 68};

        LinearSearch ls = new LinearSearch();
        int res = ls.search(data, 12);
        System.out.println(res);

        int res2 = ls.search(data, 888);
        System.out.println(res2);
    }
}

At this time, the console output is:

3
-1

As you can see, we are looking for the number 12, which is in the fourth position, that is, the position with index 3. Another number is 888, but 888 does not appear in the array, so - 1 is returned.

However, have you found that although this program seems to have been implemented, it still seems to have many new problems. What is it?

The current problem is that we can only find an int element in an int array. But in the java language, there are eight basic types alone. Not to mention, our users can also create various classes themselves, and each class can be regarded as a new type. Then it's even more impossible for us to write a search method for each class, right.

So, for such a problem? How do we solve it?

At this time, we need to use generics in the java language. Next, we will transform and upgrade according to generics.

3. Use generics

Here, let's briefly review the basic data types of java. The details are as follows:

• Generics in the java language can only accept class objects, but not basic data types.
• The 8 basic data types in java are boolean, byte, char, short, int, long, float and double.
• Because generics can only accept class objects, in order to deal with this situation, the java language makes a corresponding wrapper class for each basic data type. Then these data types and their corresponding wrapper classes can be converted to each other. Among them, the eight corresponding packaging classes are Boolean, Byte, Character, Short, Integer, Long, Float and Double.
• With the concept of wrapper class, when using generics, if the type we want to pass in is the basic data type in point ① above, we only need to convert these data types into their wrapper classes.

4. Upgrading

Above, we have a brief understanding of some basic information about generics in the java language. Now, we use the learned generics to transform the code in the original example. The specific codes are as follows:

public class LinearSearch {

    private LinearSearch() {}

    // Static method
    public static <E> int search(E[] data, E target) {

        // Linear search logic
        for (int i = 0; i < data.length; i++) {
            // ==It judges that references are equal, and equals judges that values are equal
            if (data[i].equals(target))
                return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        Integer[] data = {24, 45, 67, 12, 465, 78, 68};

        int res = LinearSearch.search(data, 12);
        System.out.println(res);

        int res2 = LinearSearch.search(data, 888);
        System.out.println(res2);
    }
}

At this time, the console output is:

3
-1

In this way, we make the flexibility of this algorithm a little stronger.

5. Using custom classes

Above, we have a basic understanding of linear search. Now, let's think about a question: can we design a Student class by ourselves? It doesn't matter what kind of member variables are in this class. Then, based on the design of Student class, we can define the equals function in this class by ourselves.

Next, we will write the code according to the above topic:

First, create a new Student class in the src directory of the project. The specific code is as follows:

public class Student {

    private String name;

    public Student(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object student) {

        if(this == student) {
            return true;
        }

        if(student == null)
            return false;

        if(this.getClass() != student.getClass())
            return false;

        Student another = (Student)student;
        return this.name.equals(another.name);
    }
}

Next, continue to transform the linearsearch Java, the specific code is as follows:

public class LinearSearch {

    private LinearSearch() {}

    // Static method
    public static <E> int search(E[] data, E target) {

        // Linear search logic
        for (int i = 0; i < data.length; i++) {
            // ==It judges that references are equal, and equals judges that values are equal
            if (data[i].equals(target))
                return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        Integer[] data = {24, 45, 67, 12, 465, 78, 68};

        int res = LinearSearch.search(data, 12);
        System.out.println(res);

        int res2 = LinearSearch.search(data, 888);
        System.out.println(res2);

        Student[] students = {new Student("Monday"),
                                new Student("Tuesday"),
                                new Student("Wednesday")};
        Student tuesday = new Student("Tuesday");
        int res3 = LinearSearch.search(students, tuesday);
        System.out.println(res3);
    }
}

Now let's look at the output of the console:

3
-1
1

As you can see, the output above is still 3 and - 1. The last output 1 is the result of our custom Student class. In this way, the flexibility of the whole program has been enhanced.

6. Loop invariant

Continue, we still learn loop invariants according to the linear search algorithm. The concept of loop invariants sounds a little theoretical. But in fact, when we use the algorithm, if we can make good use of this concept, whether we understand the algorithm or really write the algorithm, it will make it easier for us to write the correct algorithm.

Loop is a very important way to build logic in program design. In fact, we all have the concept of loop in the design of the algorithm. We always have to do one thing circularly and gradually solve the algorithm we are currently solving.

For example, for the simplest linear search method:

public static<E> int search(E[] data, E target) {
    for(int i = 0; i < data.length; i++)
        if(data[i].equals(target))
            return i;
        return -1;
}

What is the loop invariant of the above algorithm? It refers to the string of for (int i = 0; I < data. Length; I + +).

The so-called loop invariant means that the conditions of the loop are unchanged at the beginning of each round. You can imagine that if the value of the specific target cannot be matched in data[i] during the execution of each if statement, it will continue to the next for loop, and the content of this for loop is always within the interval of [0... i), so it is called loop invariant.

In the above algorithm, one of the codes:

if(data[i].equals(target))
   return i;

This code is called loop body, and its main function is to maintain loop invariants.

III 📊 Algorithm complexity

Next, let's talk about the complexity of the algorithm.

1. Simple complexity analysis

Why should we analyze the complexity of the algorithm? In fact, it is used to represent the performance of the algorithm.

For example, for the same task, we will have different algorithms to complete this task, and different algorithms also have certain differences in time performance. Therefore, we need to analyze the complexity of the algorithm to solve the optimal algorithm.

Complexity describes the change trend of algorithm performance with the increase of data scale n.

2. Common algorithm complexity

Next, let's look at the common algorithm complexity.

(1) Traverse a two-dimensional array of n * n

The specific algorithm code is as follows:

for(int i = 0; i < n; i++)
	for(int j = 0; j < n; j++)
	// Traverse to A[i][j]

The time complexity of the above algorithm is O(n) ²) .

(2) Traverse a two-dimensional array of a*a

Where a * a = n, the specific algorithm code is as follows:

for(int i = 0; i < a; i++)
    for(int j = 0; j < a; j++)
    // Traverse to A[i][j]

The time complexity of the above algorithm is O(a * a), that is, O(n). In this scenario, we need to know who n is.

(3) Number of binary digits of number n

The specific algorithm code is as follows:

while(n) {
    n % 2 // A bit in the binary of n
    n /= 2；
}

For this algorithm, its time complexity is O ( l o g 2 n ) O(log_2n) O(log2 ＾ n), what about the decimal digits of N? Its time complexity is O ( l o g 10 n ) O(log_{10}n) O(log10​n) . However, it is worth noting that the algorithm complexity based on 2 or 10 is unified as O ( l o g n ) O(logn) O(logn) . Because in the algorithm of the program, the difference of the bottom has no great impact on the actual algorithm, so they are collectively referred to as O ( l o g n ) O(logn) O(logn) complexity.

3. Complexity summary

The complexity of several common algorithms is summarized below:

O ( 1 ) < O ( l o g n ) < O n < O ( n l o g n ) < O ( n ² ) < O ( 2 n ) < O ( n ! ) O(1)<O(logn)<O\sqrt{n}<O(nlogn)<O(n²)<O(2^n)<O(n!) O(1)<O(logn)<On ​<O(nlogn)<O(n²)<O(2n)<O(n!)

4. Spatial complexity

When it comes to time complexity, we can't help thinking of space complexity. But for modern computers, the storage capacity of hard disk is getting larger and larger. At this time, the space complexity is not so important. Therefore, we usually exchange space for time to make the program better.

IV 🗂️ Test algorithm performance

Still taking the LinearSearch we mentioned above as an example, let's test the performance of the algorithm. Obviously, in the above algorithm, there are only about 10 digits, but in the actual development, the amount of calculation must be more than that small. It is generally as small as 100000, as large as tens of millions and hundreds of millions. Next, we use the above example to transform. First, create a new java class of ArrayGenerator in the src directory. The specific code is as follows:

public class ArrayGenerator {

    private ArrayGenerator() {}
    public static Integer[] generateOrderArray(int n) {

        Integer[] arr = new Integer[n];
        for(int i = 0; i < n; i++)
            arr[i] = i;
        return arr;
    }
}

Next, let's transform the LinearSearch class. The specific code is as follows:

import java.lang.reflect.Array;

public class LinearSearch {

    private LinearSearch() {}

    // Static method
    public static <E> int search(E[] data, E target) {

        // Linear search logic
        for (int i = 0; i < data.length; i++) {
            // ==It judges that references are equal, and equals judges that values are equal
            if (data[i].equals(target))
                return i;
        }
        return -1;
    }

    public static void main(String[] args) {

        // Size of data to be retrieved
        int[] dataSize = {1000000, 10000000};
        for(int n: dataSize) {
            Integer[] data = ArrayGenerator.generateOrderArray(n);
            long startTime = System.nanoTime();
            // Time to run 100 times
            for (int k = 0; k < 100; k++)
                LinearSearch.search(data, n);
            long endTime = System.nanoTime();

            double time = (endTime - startTime) / 1000000000.0;
            System.out.println("n = " + n + ", 100 runs : " + time + 's');
        }
    }
}

At this time, the display result of the console is:

n = 1000000, 100 runs : 0.3463959s
n = 10000000, 100 runs : 3.3792709s

As you can see, when n is 1 million data, the final running time is about 0.3s, while when the data is 10 million, the final running time is about 3.3s. The gap between them is about 10 times, that is, it increases linearly.

V 📆 Concluding remarks

In the above article, we learned the basic knowledge of the algorithm and the basic idea of linear search method. On this basis, the linear search method is simply implemented, and the linear search method is upgraded by using generic and user-defined classes.

Finally, we also briefly introduce the complexity analysis of the algorithm and test the performance of our algorithm.

Here, the introduction of this article is over! I wonder if you have a deeper understanding of the linear search method?

🐣 One More Thing

• Pay attention to the public Monday research room. First, pay attention to learning dry cargo. More column will be open for you to unlock official account.
• If this article is useful to you, remember to leave a footprint jio before you go~
• See you next time! 🔑🔑🔑