LinearSearch
public class LinearSearch { private LinearSearch() { } public static <A> int search(A[] data, A target) { for (int i = 0; i < data.length; i++) if (data[i].equals(target)) return i; return -1; } public static void main(String[] args) { Integer[] data = {24, 18, 12, 9, 16, 66, 32, 4}; int res = LinearSearch.search(data, 16); System.out.println(res); int res2 = LinearSearch.search(data, 126); System.out.println(res2); } }
让我们来看看一个自定义类的操作
public class LinearSearch { private LinearSearch() { } 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; } public static void main(String[] args) { // Integer[] data = {24, 18, 12, 9, 16, 66, 32, 4}; // int res = LinearSearch.search(data, 16); // System.out.println(res); // // // int res2 = LinearSearch.search(data, 126); // System.out.println(res2); Student[] students = {new Student("aaa"), new Student("ddd"),new Student("www")}; Student aaa = new Student("aaA"); int res3 = LinearSearch.search(students,aaa); System.out.println(res3); } }
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.toLowerCase().equals(another.name.toLowerCase()); } }
需要注意的点
这里我们需要注意,虽然我们重写了student,但是也是需要创建一个对象的喔。千万不要直接对比字符串,要不然也是得不到我们想要的




这里是一种设计思想,在后面可能就不会说得那么细了,未来这种思想会贯穿整个算法结构,后面的算法会越来越复杂,期待吧!
复杂度分析:表示算法的性能
咱们之前的小例子
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; }
我们先看一张图
循环体:维持循环不变量
目前我们的循环体比较简单,在后期我们复杂的算法逻辑的时候,我们才会更加清晰的了解循环不变量的意义,这里先有一个小理解!
写出正确的代码:1.定义清楚循环不变量 2.维护循环不变量 3.定义清楚函数的功能
常见的算法复杂度
空间复杂度
在现在的时代里面,我们一般不在意空间复杂度,而更加的在意时间复杂度,因为现在的计算机内存越来越大,而控件也就越来越大,所以我们更希望的是使用空间换时间!
测试时间复杂度
ArrayGenerator
public class ArrayGenerator { private ArrayGenerator() { } public static Integer[] generateOrderedArray(int n) { Integer[] arr = new Integer[n]; for (int i = 0; i < n; i++) arr[i] = i; return arr; } }
public static void main(String[] args) { int [] dataSize = {1000000,10000000}; for(int n :dataSize){ Integer[] data = ArrayGenerator.generateOrderedArray(n); long startTime = System.nanoTime(); 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"); }
控制台输出
n = 1000000,100 runs :0.1458204s
n = 10000000,100 runs :1.3222407s
本文作者为DBC,转载请注明。