认识时间复杂度
常数时间的操作:一个操作如果和数据量没有关系,每次都是 固定时间内完成的操作,叫做常数操作。
时间复杂度为一个算法流程中,常数操作数量的指标。常用O (读作big O)来表示。具体来说,在常数操作数量的表达式中, 只要高阶项,不要低阶项,也不要高阶项的系数,剩下的部分
如果记为f(N),那么时间复杂度为O(f(N))。
评价一个算法流程的好坏,先看时间复杂度的指标,然后再分 析不同数据样本下的实际运行时间,也就是常数项时间。
例子
一个简单的理解时间复杂度的例子
一个有序数组A,另一个无序数组B,请打印B中的所有不在A中的数,A数 组长度为N,B数组长度为M。
算法流程1:对于数组B中的每一个数,都在A中通过遍历的方式找一下;
算法流程2:对于数组B中的每一个数,都在A中通过二分的方式找一下;
算法流程3:先把数组B排序,然后用类似外排的方式打印所有在A中出现 的数;
三个流程,三种时间复杂度的表达...
如何分析好坏:
流程1: o(m*n)
流程2: o(mlogn)
流程3:数组B排序:o(mlogm) 外排:(n+m) o(mlogm)+(n+m)
冒泡排序
public static void maopaosort(int[] arr) { if(arr==null||arr.length<2){ return; } for (int i = arr.length-1; i>0; i--) { for (int j = 0; j <i; j++) { // 从后面开始往前排序 // 内循环是比较相邻的两个元素,把最大的元素交换到后面 if (arr[j]>arr[j+1]){ swap(arr,j,j+1); } } } } public static void swap(int[] arr, int i, int j){ int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; }
时间复杂度:等差数列,an^2+bn+1 o(n^2)
选择排序
public static void xuanzesort(int[] arr) { if(arr==null||arr.length<2){ return; } for (int i = 0; i <arr.length-1 ; i++) { int min=i; for (int j = i+1; j <arr.length ; j++) { // 每一次寻找都是\"在剩余子数组里面\"最小的那个 if(arr[j]<arr[min]){ min=j; } } swap(arr,min,i); } } public static void swap(int[] arr, int i, int j){ int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; }
时间复杂度:o(n^2)
插入排序
public static void charusort(int[] arr) { if(arr==null||arr.length<2){ return; } //每次先排好j到i范围的数,慢慢扩大范围 for (int i = 1; i <arr.length ; i++) { for (int j = i-1; j >=0; j--) { if(arr[j+1]<arr[j]){ swap(arr,j,j+1); } } } } public static void swap(int[] arr, int i, int j){ int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; }
时间复杂度:最坏:o(n^2) 最好(已经排好序):o(n)
剖析递归行为和递归行为时间复杂度的估算
符合T(N) = a*T(N/b) + O(N^d),可以使用master公式
N:父问题的样本量
a:过程发生多少次
N/b:子问题的样本量
d:除去子过程外,剩下的时间复杂度
master公式
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)
归并排序
T(N)=2(N/2)+O(N)
运用master公式2,算出时间复杂度:o(nlogn)
public static void mergeSort(int[] arr) { if(arr==null||arr.length<2){ return; } sortProcess(arr,0,arr.length-1); } public static void sortProcess(int[] arr, int L, int R) { if(L==R){ return; } //mid=L+((R-L)>>1); int mid=(L+R)/2; sortProcess(arr,L,mid); sortProcess(arr,mid+1,R); merge(arr,L,mid,R); } public static void merge(int[] arr, int L, int mid, int R) { int[] help=new int[R-L+1]; int i=0; int p1=L;//左指标 int p2=mid+1;//右指标 while(p1<=mid&&p2<=R) //左右指标比较,谁小填谁 help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++]; //p2已经越界,拷贝p1 while(p1<=mid) help[i++]=arr[p1++]; //p1已经越界,拷贝p2 while(p2<=R) help[i++]=arr[p2++]; for(int j=0;j<help.length;j++) arr[L+j]=help[j]; }
例子:小和问题
在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。求一个数组 的小和。
例子:
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
public class SmallSum { public static void main(String[] args) { int[] arr={1,3,4,2,5}; System.out.println(smallSum(arr)); } public static int smallSum(int[] arr) { if(arr==null||arr.length<2){ return 0; } return mergeSort(arr,0,arr.length-1); } public static int mergeSort(int[] arr,int l,int r){ if(l==r) return 0; int mid=(l+r)/2; return mergeSort(arr,l,mid)+mergeSort(arr,mid+1,r)+merge(arr,l,mid,r); } public static int merge(int[] arr,int l,int mid,int r){ int res=0; int[] help=new int[r-l+1]; int i=0; int p1=l; int p2=mid+1; while(p1<=mid&&p2<=r){ res+=arr[p1]<arr[p2]?(r-p2+1)*arr[p1]:0; help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++]; } while(p1<=mid) help[i++]=arr[p1++]; while(p2<=r) help[i++]=arr[p2++]; for (int j = 0; j <help.length; j++) { arr[l+j]=help[j]; } return res; } }