线性查找法
一、 什么是算法
算法的五大特性 二、 使用泛型
代码： 三、 使用自定义类测试我们的算法四、 循环不变量五、 简单的复杂度分析六、 测试算法性能七、 总结 线性查找法
一个非常简单的算法适应更多的数据类型如何编写正确的程序性能测试复杂度分析 一、 什么是算法
Algorithm：一系列解决问题的、清晰的、可执行的计算机指令
算法的五大特性 有限性确定性：不会产生二义性可行性输入输出 二、 使用泛型 代码：简单写一下：
public class LinearSearch { private LinearSearch(){} //不希望用户创建LinearSearch类的对象，用户只需要使用方法就好。 // 根据题意，我们返回的是目标的索引值 public static int search(int[] data, int target){ 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, 18, 12, 9, 16, 66, 32, 4}; int res = LinearSearch.search(data,16); System.out.println(res); int res2 = LinearSearch.search(data,666); System.out.println(res2); }}
4
-1
改造：因为现在我们只能在int类型使用，所以使用泛型进行改进
泛型：
不可以是基本数据类型，只能是类对象八种数据类型：boolean, byte, char, short, int, long, float, double每个基本数据类型都有对应的包装类八种数据类型对应的包装类：Boolean, Byte, Character, Short, Integer, Long, Double
//Java中最常使用的泛型定义方式就是泛型类，现在我们只需要改算法，所以没必要写泛型类public class LinearSearch { private LinearSearch(){} //不希望用户创建LinearSearch类的对象，用户只需要使用方法就好。 // 根据题意，我们返回的是目标的索引值 public static
任务：设计一个Student类
public class Student { private String name; public Student(String name){ this.name = name; }}
public class LinearSearch { private LinearSearch(){} public static
结果是-1，这是因为我们的equals方法有问题，所以我们需要自定义equals：
public class Student { private String name; public Student(String name){ this.name = name; } //euqals(Student studnet)是不对的，因为equals是Object父类的方法，我们要覆盖它就要传父类 @Override public boolean equals(Object student){ // 强制转换可能出异常，我们判断一下 //当前的对象是否是student类的对象，地址是否一样，也就是是否是同一对象 if (this == student){ return true;} //传来的student是不是空对象 if (student == null){ return false;} //判断强制转换是否成功 if (this.getClass() != student.getClass()){ return false; } //强制类型转换，这样就可以进行字符串的比较a Student another = (Student)student; return this.name.equals(another.name); }}
如果我们还想忽略大小写进行比较：
public class Student { private String name; public Student(String name){ this.name = name; } //euqals(Student studnet)是不对的，因为equals是Object父类的方法，我们要覆盖它就要传父类 @Override public boolean equals(Object student){ // 强制转换可能出异常，我们判断一下 //当前的对象是否是student类的对象，地址是否一样，也就是是否是同一对象 if (this == student){ return true;} //传来的student是不是空对象 if (student == null){ return false;} //判断强制转换是否成功 if (this.getClass() != student.getClass()){ return false; } //强制类型转换，这样就可以进行字符串的比较a Student another = (Student)student; //转换成小写进行比较 return this.name.toLowerCase().equals(another.name.toLowerCase()); }}
四、 循环不变量
复杂度分析：表示算法的性能，通常看最差的情况
复杂度描述的是随着数据规模n的增大，算法性能的变化趋势，所以常数不重要
数据规模我们通常使用n来表示，在这个例子里面n = data.length，时间复杂度为 O ( n ) O_{(n)} O(n)
T 1 T_1 T1=10000n T 2 T_2 T2= 2 n 2 2n^2 2n2 两个之间进行比较：
O ( n ) O_{(n)} O(n) O ( n 2 ) O_{(n^2)} O(n2)
时间复杂度：
O ( 1 ) O_{(1)} O(1) < O ( l o g n ) O_{(logn)} O(logn) < O ( n ) O_{(sqrt n)} O(n ) < O ( n ) O_{(n)} O(n) < O ( n l o g n ) O_{(nlogn)} O(nlogn) < O ( n 2 ) O_{(n^2)} O(n2) < O ( 2 n ) O_{(2^n)} O(2n) < O ( n ! ) O_{(n!)} O(n!)
public class LinearSearch { private LinearSearch(){} public static
结果：
七、 总结n = 1000000, 100 runs : 0.1247484 s
n = 10000000, 100 runs : 1.2319889 s
线性查找法使用泛型：泛型方法使用自定义的类如何编写正确的程序：循环不变量复杂度分析测试算法性能