算法 ： 算法是一组完成任务的指令，任何代码片段都可视为算法。
对数运算：对数运算是幂运算的逆运算。
注意：仅当列表为有序的时候，二分查找才管用。
简单查找的运行时间为线性时间，二分查找的运行时间为对数时间。
大O表示法：是一种特殊的表示法，指出了算法的速度有多快。
大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速。
常见的大O运行时间
- O(log n)，也叫对数时间，这样的算法包括二分查找。
- O(n)，也叫线性时间，这样的算法包括简单查找。
- O(n * log n)，这样的算法包括快速排序。
- O(n2)，这样的算法包括选择排序。
-
O(n!)，这样的算法包括旅行商问题的解决方案。迭乘：5 * 4 * 3 * 2 * 1
二分查找程序
package com.study;
import java.util.Arrays;
import java.util.List;
public class BinarySearchTest {
public static void main(String[] args) {
List<Integer> list = Arrays.asList(1,2,3,4,5,6,8,11,15,17);
Integer item = 1;
Integer result = binarySearch(list,item);
System.out.println(result);
}
public static Integer binarySearch(List<Integer> list, Integer item) {
int low = 0;
int high = list.size() - 1;
while (low <= high) {
int center = (low + high) / 2;
if (list.get(center) > item) {
high = center - 1;
} else if (list.get(center) < item){
low = center + 1;
} else {
return center;
}
}
return null;
}
}
选择排序
package com.study;
public class SelectSortTest {
public static void main(String[] args) {
int[] arr = new int[]{1,3,2,8,7,4,6};
int arrLength = arr.length;
for (int i = 0; i < arrLength; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
}
