线性查找法
线性查找法
- 一个非常简单的算法
- 适应更多的数据类型
- 如何编写正确的程序
- 性能测试
- 复杂度分析
一、 什么是算法
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 <E> int search(E[] data, E target){
for (int i = 0; i < data.length; i++) {
//此时的data已经不是一个基本数据类型了,所以不能使用==,==判断的是引用相等;这里是两个类对象进行比较,我们使用equals()
if (data[i].equals(target)) {
return i;
}
}
return -1;
}
public static void main(String[] args){
//在Java中泛型只能接受类对象,为不能接受基本数据类型
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,666);
System.out.println(res2);
}
}
三、 使用自定义类测试我们的算法
任务:设计一个Student类
public class Student {
private String name;
public Student(String name){
this.name = name;
}
}
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){
Student[] students = {new Student("Alice"),
new Student("Bobo"),
new Student("Charles")};
Student bobo = new Student("Bobo");
int res3 = LinearSearch.search(students,bobo);
System.out.println(res3);
}
}
结果是-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 <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){
int[] datasize = {1000000, 10000000};
for (int n : datasize) {
Integer[] data = ArrayGenerator.generateOrderedArray(n);
//计时
long startTime = System.nanoTime(); //时间戳
for (int i = 0; i < 100; i++) {
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.1247484 s
n = 10000000, 100 runs : 1.2319889 s
七、 总结
- 线性查找法
- 使用泛型:泛型方法
- 使用自定义的类
- 如何编写正确的程序:循环不变量
- 复杂度分析
- 测试算法性能