程序=算法(解决问题的步骤)+数据结构(合理的持有数据)
* 如何衡量算法的优劣?
1、计算时间
long start=System.currentTimeInMills();
处理步骤;
long end=System.currentTimeInMills();
System.out.println("该算法用时"+(end-start)+"ms");
2、时间复杂度
是一个用于度量一个算法的运算时间的一个描述,本质是一个函数,根据
这个函数能在不用具体的测试数据来测试的情况下,粗略地估计算法的执
行效率
查找一个算法中执行次数最多的部分和算法规模的相互关系--函数
常用大O来表述,这个函数描述了算法执行所要时间的增长速度
常量阶 O(1)
对数阶 O(logn)
线性阶 O(n)
线性对数阶 O(nlogn)
n方阶 O(nⁿ)
指数阶 O(2ⁿ)
阶乘阶 O(n!)
示例
public class Test1 {public static void main(String[] args) {int[] arr = new int[] { 1, 6, 2, 4, 3, 7, 9, 8 };for (int i = 1; i < arr.length; i++) { // 7for (int k = 0; k < arr.length - i; k++) { // 7 6 5 ... (n-1)*n/2if (arr[k] > arr[k + 1]) {int tmp = arr[k];arr[k] = arr[k + 1];arr[k + 1] = tmp;}}}System.out.println(Arrays.toString(arr));// 时间复杂度为 n^2/2-n/2 时间和问题规模n成正相关关系// 使用大O计法时,只保留最高次幂,去掉所有常量O(n^2)// 折半查找int target = 6;int min = 0;int max = arr.length - 1;int pos = (min + max) / 2;while (min <= max) {pos=(min + max) / 2;if (arr[pos] > target) {max = pos - 1;} else if (arr[pos] < target) {min = pos + 1;} else if (arr[pos] == target)break;}System.out.println("位置为:" + pos);//2^k=n k以2为底n的对数 时间复杂度为O(logN)}}