什么是算法
一系列解决问题的，清晰的，可执行的计算机指令。
- 有限性
- 确定性： 不会产生二义性。不是说确定的输入就有确定的输出。
- 可行性。
- 输入（广义上的）
- 输出（广义上的）
线性查找法
网络异常，图片无法展示
|
根据上面的案列，简单设计一个线性查找函数。
public class LinerSearch { public static int getLinerSearch(int[] arr, int target) { for(int i = 0; i < arr.length; i++) { if(arr[i] == target) { return i; } } return -1; } @Test public void test1() { int[] arr = new int[]{24, 18, 12, 9, 16, 66, 32, 4}; int linerSearch = LinerSearch.getLinerSearch(arr, 16); System.out.println(linerSearch); // 4 } }
通过上面的测试可以发现，是没问题的，很简单。但是有一个问题，他只是满足int类型的数组。所以我们可以使用泛型让其可以适合任何类型的线性查找。
public class LinerSearch { public static <E> int getLinerSearch(E[] arr, E target) { for(int i = 0; i < arr.length; i++) { // 这里需要通过equals判断，因为可能出现比较错误。 if(arr[i].equals(target)) { return i; } } return -1; } @Test public void test1() { Integer[] arr = new Integer[]{24, 18, 12, 9, 16, 66, 32, 4}; int linerSearch = LinerSearch.getLinerSearch(arr, 16); System.out.println(linerSearch); // 4 } }
注意，我们在判断自定义类的查找时，一定要在类中重写equals方法。下面我们来看一下自定义类的线性查找吧。
public class Student { private String name; public Student(String name) { this.name = name; } // 重写equals方法 @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; return name != null ? name.equals(student.name) : student.name == null; } }
@Test public void test2() { Student[] arr = new Student[] { new Student("zh"), new Student("llm"), new Student("jcl") }; int linerSearch = LinerSearch.getLinerSearch(arr, new Student("llm")); System.out.println(linerSearch); // 1 }
复杂度分析
// 算法性能测试 @Test public void test3() { int n = 1000000; int count = 100; long start = new Date().getTime(); for(int i = 0; i < count; i++) { // 查询count次 // LinerSearch.resultArr(n). 返回传入的n长度的数组。 LinerSearch.getLinerSearch(LinerSearch.resultArr(n), n); } long end = new Date().getTime(); System.out.println((end - start) / 1000 + "s"); }
循环不变量
在每一次循环开始的时候，都满足一种条件。循环体是维持循环不变量的。他也是“证明”程序正确性的。
网络异常，图片无法展示
|
复杂度分析
- 表示算法的性能。
- 算法运行的上界。
- 常数不重要。
- 复杂度描述的是随着数据规模n的增大，算法性能的变化趋势。
网络异常，图片无法展示
|
常见复杂度比较
网络异常，图片无法展示
|
