一、认识复杂度
1.评估算法优劣的核心指标:
时间复杂度:当完成了表达式的建立,只要把最高阶项留下即可。低阶项都去掉,高阶项的系数也去掉,记为O(去掉系数的高阶项);
时间复杂度是衡量算法流程的复杂度的一种指标,该指标只与数据量有关,与过程之外的优化无关
常见的时间复杂度(从好到坏)
O(1)
O(logN)
O(N)
O(N+logN)
O(N2),O(N3)....O(N^K)
O(2^N) O(#N)...O(KN)
O(N!)
空间复杂度
常数项时间
说明:如何确定算法流程的总操作数与样本数量之间的表达式关系?
(1)想象该算法流程所处理的数据状况,要按照最差情况来
(2)把整个流程彻底拆分为一个个基本动作,保证每个动作都是常数时间的操作
(3)如果数据量为N,看看基本动作的数量和N是什么关系
2.通过排序,实现时间复杂度的估算
2.1 选择排序
- 基本思想
首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
- 实现逻辑
① 第一轮从下标为 1 到下标为 n-1 的元素中选取最小值,若小于第一个数,则交换
② 第二轮从下标为 2 到下标为 n-1 的元素中选取最小值,若小于第二个数,则交换
③ 依次类推下去……
//将数组中的数从下到大排序
public static void selectionSort(int[] arr){
//如果数值中只有一个数,返回
if(arr == null || arr.lenght<2){
return;
}
//遍历数组按从小到大排序
for(int i=0;i<arr.length-1;i++){
//最小值的位置索引
int minIndex=i;
for(int j=i+1;j<arr.length;j++){
mindex=arr[j]<arr[minIndex]?j:minIndex;
}
//交换两个数的位置
swap(arr,i,minindex);
}
}
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];
}
- 复杂度分析
平均时间复杂度:O(N^2)
最佳时间复杂度:O(N^2)
最差时间复杂度:O(N^2)
空间复杂度:O(1)
排序方式:In-place
稳定性:不稳定
2.2 冒泡排序
- 基本思想
冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
- 算法步骤
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较 。
//将数组中的数从下到大排序
public static void selectionSort(int[] arr){
//如果数值中只有一个数,返回
if(arr == null || arr.lenght<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);
}
}
}
}
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];
}
2.3插入排序
- 基本思想
插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
- 算法步骤
将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)
//将数组中的数从下到大排序
public static void selectionSort(int[] arr){
//如果数值中只有一个数,返回
if(arr == null || arr.lenght<2){
return;
}
//0~0是有序的
//0~i 变成有序
for(int i=0;i<arr.length-1;i++){
//最小值的位置索引
//arr[i]与arr[i-1],arr[i-2]...比较,如果小就往前交换,一直交换到合适的位置停止
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];
}
3、额外空间复杂度
你要实现一个算法流程,在实现算法流程的过程中,你需要开辟一些空间来支持你的算法流程。
作为输入参数的空间,不算额外空间。
作为输出结果的空间, 也不算额外空间。
因为这些都是必要的、和现实目标有关的。所以都不算。
但除此之外,你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空
间就是额外空间。
如果你的流程只需要开辟有限几个变量,额外空间复杂度就是O(1)。
4、算法流程的常数项
我们会发现,时间复杂度这个指标,是忽略低阶项和所有常数系数的。难道同样时间复杂度的流程,在实际运行时候就一样的好吗?
当然不是。
时间复杂度只是一个很重要的指标而已。如果两个时间复杂度一样的算法,你还要去在时间上拼优劣,就进入到拼常数时间的阶段,简称拼常数项。
补充说明:一个问题的最优解是什么意思?
一般情况下,认为解决一个问题的算法流程,在时间复杂度的指标上,一定要尽可能的低,先满足了时间复杂度最低这个指标之后,使用最少的空间的算法流程,叫这个问题的最优解。
一般说起最优解都是忽略掉常数项这个因素的,因为这个因素只决定了实现层次的优化和考虑,而和怎么解决整个问题的思想无关。
二、认识对数器
1,你想要测的方法a
2,实现复杂度不好但是容易实现的方法b3,实现一个随机样本产生器
4、把方法a和方法b跑相同的随机样本,看看得到的结果是否一样
5,如果有一个随机样本使得比对结果不一致,打印样本进行人工干预,改对方法a和方法b
6,当样本数量很多时比对测试依然正确,可以确定方法a已经正确。
案例说明:产生一个随机数组
public static int[] generateRandomArray(int maxSize,int maxValue){
//Math.random():返回[0,1)范围一个随机小数
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+1)*Math.random())
}
return arr;
}
三、认识二分法
1)在一个有序数组中,找某个数是否存在
2)在一个有序数组中,找>=某个数最左侧的位置
3)在一个有序数组中,在<=某个数最右侧 的位置
- 局部最小值问题
1.有序数组使用二分法
public static boolean exist(int[] sortedArr,int num){
if(sortedArr == null || sortedArr.length==0){
return false;
}
int L=0;//左索引
int R=sortedArr.length-1;//右索引
int mid=0;//中间位置索引
while(L<R){
mid=L+((R-L)>>1);//等价于mid=(L+R)/2
if(sorteArr[mid]==num){
return ture
}else if(sottArr[mid]>num){
R=mid-1;
}else{
L=mid+1;
}
return sortArr[L]==num;
}
}
2.无序数组且相邻不等使用二分法
public static int getLessIndex(int[] arr){
//判断数组是否为空
if(arr==null || arr.length==0){
return -1;
}
//判断是否只有一个数据,或者有两个数据,但arr[0]<arr[1]
if(arr.length==1 || arr[0]<arr[1]){
return 0;
}
//判断最后一个是否是小的
if(arr[arr.length-1]<arr[arr.length-2]){
return arr.length-1;
}
int left=1;
int right=arr.length-2;
int mid=0;
while(left<right){
mid=(left+right)/2;
if(arr[mid]>arr[mid-1]){
right=mid-1;
}else if(arr[mid]>arr[mid+1]){
left=mid+1;
}else{
return mid;
}
}
return left;
}
四、认识异或运算
1.异或运算:相同为0,不同为1
同或运算:相同为1,不同为0
2.异或运算的性质
- 0^N=N N^N=0
- 异或运算满足交换律与结合律
举例:如何取出一个整型数最右侧的1(以二进制为例)
比如一个整数N:001101010000
则需要输出: 000000010000
方法:N&((~N)+1)(即N与N的取反加1进行与运算)
原理:
N: 001101010000
~N: 110010101111
~N+1: 110010110000
N&((~N)+1):000000010000
说明:上述例子可应用于多种算法中,如以下例题
给一个整数数组arr,有两个不同的数出现了奇数次,找出这两个数
//假设出现奇数次的数为a,b
public static void printOddTImesNum2(int[] arr){
for eor=0;
for(int i =0;i<arr.length;i++){
eor ^=arr[i];//此时eor的值为a^b的值
//eor=a^b
//且eor !=0
//所以eor(二进制)必然有一个位置上是1
//为了确定这个位置,我们考虑找出最右侧的1的位置p
//保留位置p的数的值
int rightOne=eor & (~eor+1);
//找出最右侧的1的位置p 后,我们将数组分为两类,
//一类是位置p上为1的,一类是位置p上不为1的
//选择其中一类进行异或运算eor1 ^=arr[i]可得出a或b其中一个数
//则另一个数进行eor1 ^eor 可得出
int onlyOne=0;//eor1
for(int i=0;i<arr.length:i++){
//找到位置p上是1 的那一类数
if((arr[i] & rightOne) !=0){
onlyOne ^=arr[i];
}
}
System.out.println(onlyOne+" "+(eor^onlyOne));
}
}
标签:arr,int,复杂度,元素,算法,二分法,异或,排序
From: https://www.cnblogs.com/jiaxh/p/17794097.html