算法初级01——认识时间复杂度、对数器、 master公式计算时间复
虽然以前学过,再次回顾还是有别样的收获~ ? 认识时间复杂度
? ? 例子一一个简单的理解时间复杂度的例子 ? 一个有序数组A,另一个无序数组B,请打印B中的所有不在A中的数,A数组长度为N,B数组长度为M。 ?算法流程1:对于数组B中的每一个数,都在A中通过遍历的方式找一下; ?算法流程2:对于数组B中的每一个数,都在A中通过二分的方式找一下; ?算法流程3:先把数组B排序,然后用类似外排的方式打印所有在A中出现的数; ?三个流程,三种时间复杂度的表达... ?如何分析好坏? ? ? 例子二?对数器的概念和使用 ?0,有一个你想要测的方法a, ?1,实现一个绝对正确但是复杂度不好的方法b, ?2,实现一个随机样本产生器 ?3,实现比对的方法 ?4,把方法a和方法b比对很多次来验证方法a是否正确。 ?5,如果有一个样本使得比对出错,打印样本分析是哪个方法出错 ?6,当样本数量很多时比对测试依然正确,可以确定方法a已经正确。 import java.util.Arrays; public class Code_01_InsertionSort { public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr,j,j + 1); } } } public static void swap(int[] arr,int i,int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } // for test public static void comparator(int[] arr) { Arrays.sort(arr); } // for test public static int[] generateRandomArray(int maxSize,int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for test public static boolean isEqual(int[] arr1,int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } // for test public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for test public static void main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize,maxValue); int[] arr2 = copyArray(arr1); insertionSort(arr1); comparator(arr2); if (!isEqual(arr1,arr2)) { succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize,maxValue); printArray(arr); insertionSort(arr); printArray(arr); } } ? 例子三? ?冒泡排序细节的讲解与复杂度分析 时间复杂度O(N^2),额外空间复杂度O(1) public static void bubbleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int e = arr.length - 1; e > 0; e--) { for (int i = 0; i < e; i++) { if (arr[i] > arr[i + 1]) { swap(arr,i,i + 1); } } } } ? 例子四选择排序的细节讲解与复杂度分析 ?时间复杂度O(N^2),额外空间复杂度O(1) ? public static void selectionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { minIndex = arr[j] < arr[minIndex] ? j : minIndex; } swap(arr,minIndex); } } ? ? ? 例子五插入排序(类似整理扑克牌)的细节讲解与复杂度分析 时间复杂度O(N^2),额外空间复杂度O(1) public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr,j + 1); } } } ? 例子六剖析递归行为和递归行为时间复杂度的估算 ?一个递归行为的例子 ?master公式的使用 ?T(N) = a*T(N/b) + O(N^d)??[a是过程发生次数,N/b是子问题,O(N^d)剩下的时间复杂度] ? 1)?log(b,a) > d -> 复杂度为O(N^log(b,a)) ?2)?log(b,a) = d -> 复杂度为O(N^d * logN) ?3)?log(b,a) < d -> 复杂度为O(N^d) ?? 补充阅读:www.gocalf.com/blog/algorithm-complexity-and-master-theorem.html ? 例子七归并排序的细节讲解与复杂度分析 时间复杂度O(N*logN),额外空间复杂度O(N) public static void mergeSort(int[] arr) { if (arr == null || arr.length < 2) { return; } mergeSort(arr,0,arr.length - 1); } public static void mergeSort(int[] arr,int l,int r) { if (l == r) { return; } int mid = l + ((r - l) >> 1); mergeSort(arr,l,mid); mergeSort(arr,mid + 1,r); merge(arr,mid,r); } public static void merge(int[] arr,int m,int r) { int[] help = new int[r - l + 1]; int i = 0; int p1 = l; int p2 = m + 1; while (p1 <= m && p2 <= r) { help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; } while (p1 <= m) { help[i++] = arr[p1++]; } while (p2 <= r) { help[i++] = arr[p2++]; } for (i = 0; i < help.length; i++) { arr[l + i] = help[i]; } } ? 例子八小和问题和逆序对问题 ? 小和问题 在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。求一个数组的小和。 ? 例子: ?[1,3,4,2,5] ?1左边比1小的数,没有; ?3左边比3小的数,1; ?4左边比4小的数,1、3; ?2左边比2小的数,1; ?5左边比5小的数,1、3、4、2; ?所以小和为1+1+3+1+1+3+4+2=16 ? 逆序对问题 ?在一个数组中,左边的数如果比右边的数大,则折两个数构成一个逆序对,请打印所有逆序对。 1 public static int smallSum(int[] arr) { 2 if (arr == null || arr.length < 2) { 3 return 0; 4 } 5 return mergeSort(arr,arr.length - 1); 6 } 7 8 public static int mergeSort(int[] arr,int r) { 9 if (l == r) { 10 return 0; 11 } 12 int mid = l + ((r - l) >> 1); 13 return mergeSort(arr,mid) + mergeSort(arr,mid + 1,r) + merge(arr,r); 14 } 15 16 public static int merge(int[] arr,int r) { 17 int[] help = new int[r - l + 1]; 18 int i = 0; 19 int p1 = l; 20 int p2 = m + 1; 21 int res = 0; 22 while (p1 <= m && p2 <= r) { 23 res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0; 24 help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; 25 } 26 while (p1 <= m) { 27 help[i++] = arr[p1++]; 28 } 29 while (p2 <= r) { 30 help[i++] = arr[p2++]; 31 } 32 for (i = 0; i < help.length; i++) { 33 arr[l + i] = help[i]; 34 } 35 return res; 36 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |