eg:123456
N-1 N-2 N-3……
等差数列,O(N²)
选择排序、冒泡排序细节的讲解与复杂度分析
时间复杂度O(N^2),额外空间复杂度O(1)
每一轮比较都是独立的,大量信息被丢弃,比较很多次只搞定了一个数。
斗地主
eg:123456
.
时间复杂度:数据状况不同,会导致算法流程的时间复杂度不一样。指按照算法可能遇到的最差情况进行估计。
等差数列:O(N²)
只用看一遍:O(N)
插入排序细节的讲解与复杂度分析
时间复杂度O(N^2),额外空间复杂度O(1)
算法流程按照最差情况来估计时间复杂度
public static void insertionSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
// 0~0有序的,天然就做到了
// 0~i 有序
for (int i=1;i //0~i有序
for (int j=i-1; j>=0 && arr[j]>arr[j+1];j--){
swap(arr, j, j+1)
}
}
}
// if i and j are in the same position,it will cause error.不要这样写
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];
}
public static void comparator(int[] arr){
Arrays.sort(arr);
}
对数器
有一个想要测的方法a,有一个好实现但时间复杂度不好的方法b。线上og是什么?
随机样本产生器:产生随机数据
在方法a里跑一遍,产生结果1
在方法b里跑一遍,产生结果2
用人工干预的结果把两个方法都改对
Math.random() # [0,1)范围内的所有小数,等概率范回一个
Math.random() * N # [0,N)范围内的所有小数,等概率范回一个
int(Math.random() * N) # [0,N-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 * Math.random());
}
return res;
对数器的概念和使用
1,有一个你想要测的方法a
2,实现复杂度不好但是容易实现的方法b
3,实现一个随机样本产生器
4,把方法a和方法b跑相同的随机样本,看看得到的结果是否一样。
5,如果有一个随机样本使得比对结果不一致,打印样本进行人工干预,改对方法a或者
方法b
6,当样本数量很多时比对测试依然正确,可以确定方法a已经正确。
剖析递归行为和递归行为时间复杂度的估算
用递归方法找一个数组中的最大值,系统上到底是怎么做的?
master公式的使用:T(N) = a*T(N/b) + O(N^d)
,前为底数。一旦a, b, d确定,则时间复杂度可以直接得出:
- log(b,a) > d -> 复杂度为O(N^log(b,a))
- log(b,a) = d -> 复杂度为O(N^d * logN)
- log(b,a) < d -> 复杂度为O(N^d)
讲解:
T(N):母问题的数据量是n级别的(n个数据)
T(N/b):N/b规模的子问题(子问题的规模是一样的)
a:子问题规模等量的情况下的调用次数
O(N^d):除调用子问题之外,剩下的过程的时间复杂度
只要满足子问题等规模的递归,都可以用master公式直接求解时间复杂度。
递归方法:求最大值
process是母问题
L~R上有N个数
子问题的规模是否是等量的:2/N,因为[L, mid] [mid, L]
子问题之外,有一个求mid的过程,时间复杂度是O(1)
因为分为两部分,所以b=2
master公式:T(N) = 2*T(N/2) + O(1)
a = 2, b = 2, d = 0,
log(2,2) = 1 > d,所以时间复杂度为O(N^log(2,2)) = O(N)
将母问题等分为三份:
master公式:T(N) = 3*T(N/3) + O(1)
a = 3, b = 3, d = 0
log(3,3) = 1 > d,所以时间复杂度为O(N^log(3,3)) = O(N)
将母问题等分为三份,并把每部分的最大值打印出来:
master公式:T(N) = 3*T(N/3) + O(N)
a = 3, b = 3, d = 1
log(3,3) = 1 = d,所以时间复杂度为O(N^1*log(N)) = O(N^log(N))
说明递归行为的时间复杂度是O(N),等效于用从左到右遍历的方法求最大值。
class2
归并排序(排序+merge每年必出) 1)整体就是一个简单递归,左边排好序、右边排好序、让其整体有序左神讲merge
2)让其整体有序的过程里用了外排序方法(即把内容拷贝到外部,如help中,然后再拷贝回来)左侧排好序[L, Mid],右侧排好序[Mid, R],然后merge整合
符合master公式求解时间复杂度:T(N) = 2 * T(N/2) + O(N),
log(2,2) = 1 = d,所以时间复杂度为O(N* logN)
.
额外空间复杂度O(N):最多只用准备N个额外空间就够了。每次准备一个空间,用完就释放了。
3)归并排序的实质merge
首先准备一个辅助空间,辅助空间的范围由[L, R]的范围决定共[R - L + 1]个数
i = 0,专门给help使用
p1指左侧部分的下标
p2指右侧部分的下标
如果没越界:谁小,谁拷贝到help里(相等时默认拷贝左边的)。
#下面两个while只会中一个
如果p1没越界,就把p2剩下的东西拷贝到help里;
如果p2没越界,就把p1剩下的东西拷贝到help里;
把help里的东西拷贝到原array中去。
merge的时间复杂度是O(N):
1、把所有的数拷贝近help里是O(N);
2、把help里的东西拷贝进原始数组是O(N)
归并排序时间复杂度log(N*logN),没有浪费比较行为,每一次比较行为都变成了有效的东西。比冒泡排序和插入排序log(N)好。
归并排序的扩展小和问题和逆序对问题
小和问题在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。求一个数组的小和。
例子:[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、暴力求解:每个都左边遍历一下,时间复杂度O(N²)
2、归并排序:
笔记:小和的另一种求法
1在右侧范围找到了一个数比1大,所以是1个1
一层一层往上归并
分批不遗漏地找到,每一个数都不漏算,也不重算。
左右两组merge时会产生小和,左侧内部与右侧内部不产生小和。相等时要保证右组先拷贝(这一步与传统merge不同)。
排序过程不可以省略
help[i++] = arr[p1]表示:当左侧不比右侧小时,把右侧拷贝进来,右侧++。左侧比右侧小时,把左侧拷贝进来,左侧++。
不重也不漏:任何一个数
在一个数组中,左边的数如果比右边的数大,则这两个数构成一个逆序对,请找到逆序数的数量,打印所有逆序对。
[3, 2, 4, 5, 0]
3, 2 、 3, 0 、 2, 0 、 4, 0 、 5, 0
堆结构远比堆排序重要。
1,堆结构就是用数组实现的完全二叉树结构(即:满二叉树)2,完全二叉树中如果每棵子树的最大值都在顶部就是大根堆数组可以写为二叉树
.
左孩子
右孩子
父
i表示索引
3,完全二叉树中如果每棵子树的最小值都在顶部就是小根堆 4,堆结构的heapInsert与heapify操作(堆结构的其余东西都是从这两个东西调出来的)以6为头的整棵树,6最大
以5为头的整棵树,5最大
以4为头的整棵树,4最大
所有父都比子大
heapInsert:向上调整
把二叉树调整成大根堆:heapInsert,俗称”篡位算法”
如果当前位置>父位置,就交换
while停止的条件有两个:①当前位置不再比父大了;②当前位置来到了0位置,不再比自己大了。
heapify:向下调整
问题:返回最大值并移出,同时让剩下的数字也是大根堆。
把0位置的值赋给一个变量,然后将树中最后一个数放到0位置。
hipesize--,让最小的孩子与整个结构断联,并且上到0位置
0位置与自己的左孩子和右孩子pk,和大于自己的那个孩子交换位置。直到自己比孩子大时停止。
↓
code:
可以从任意位置开始,往下做
①由heapsize管索引,一旦超出heapsize(越界),就认为没有孩子了。
②左孩子的下标一定比右孩子的下标小。如果左孩子下标越界,自然就不存在右孩子了。
while
当有右孩子,并且右孩子的值大于左孩子的值,则右孩子胜出,否则左孩子胜出。
如果较大孩子的值>父亲,则把较大孩子的下标给largest,否则把父亲的下标给largest。
如果largest==父亲的索引,则停止
交换最大值与父亲,并将新上位的值(新父亲)的索引给index。新的左孩子为新父亲的左孩子。
5,堆结构的增大和减少数组中有N个数
最底层节点的个数基本为N/2:最后一层没有孩子,只用看一眼,heaptify不移动。代价为1
倒数第二层节点的个数为N/4:看一眼+heaptify,代价为2
倒数第二层节点的个数为N/8:看一眼+heaptify,代价为3
……
整体复杂度为:
T(N) = N/2 + (N/4)*2 + (N/8)*3 + ……
两边*2:
2T(N) = N + (N/2)*2 + (N/4)*3 + ……
错位相减:
T(N) = N/2 + (N/4) + (N/8) + …… = 等比数列求和,时间复杂度为O(N)
6,优先级队列结构,就是堆结构 堆排序完全二叉树有N个节点,高度是logN。
所以:
①用户新加入一个数字,调整的代价是O(logN)级别。
②用户删除一个数字,调整的代价是O(logN)级别。
1,先让整个数组都变成大根堆结构,建立堆的过程:
1)从上到下的方法,时间复杂度为O(NlogN)
2)从下到上的方法,时间复杂度为O(N)
2,把堆的最大值和堆末尾的值交换,然后减少堆的大小之后,再去调
整堆,一直周而复始,时间复杂度为O(NlogN)
3,堆的大小减小成0之后,排序完成
堆排序扩展题目①数组(最开始不构成堆,heapsize=0):
②整个数组整体变成大根堆:【变成大根堆的复杂度是O(NlogN)】
对于一个数组,从左到右读取相当于用户一个一个给数字并将其装填为二叉树,装填的每一步都将其用heapInsert将其调整为大根堆,同时heapsize++
.
③把堆的0位置的数与最后位置做交换,heapsize–(把来到最后位置的最大值与整个二叉树断掉联系)
④将剩下的数字继续变成大根堆
.
⑤把堆的0位置的数与最后位置做交换,heapsize–(与③操作相同)
⑥剩下的数字继续变成大根堆
……不断重复③④类似的步骤
题目:已知一个几乎有序的数组,几乎有序是指,如果把数组排好顺序的话,每个元素移动的距离可以不超过k,并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
分析:假设k=6,准备一个小根堆。
遍历数组【0, 1, 2, 3, 4, 5, 6, 7, 8, 9】,把前k个放进小根堆【0, 1, 2, 3, 4, 5, 6】。那么小根堆最小的元素一定要在小根堆的0位置【0】,因为任何元素排序时移动的距离都不超过6。所以7以及后面的数不可能在0位置上。
把小根堆的最小值【0】弹出,然后把7扔进小根堆。【1, 2, 3, 4, 5, 6, 7】
把小根堆的最小值【1】弹出,然后把8扔进小根堆。【2, 3, 4, 5, 6, 7, 8】
把小根堆的最小值【2】弹出,然后把9扔进小根堆。【3, 4, 5, 6, 7, 8, 9】
最后临近结束时,只需要依次把小根堆的最小值弹出即可。这样整个数组都是有序的。
复杂度是O(N*logk),若k很小,可近似认为是复杂度是O(N)。
堆结构:
1、扩容的次数算上,也只是O(N)水平。
2、使用系统提供的堆结构(可认为是一个黑盒),不自己改。你给黑盒一个,它给你一个。你不能在黑盒内部搞东搞西。如果想更改,必须自己手写堆。
for:index<=k时,先把前k+1个数放到小根堆里
heap.add():加一个数到小根堆里;
heap.poll():弹一个数出去
优先级FIFO是什么?
荷兰国旗问题
题目1:【<=num】【>num】不要求有序
给定一个数组arr和一个数num,请把小于等于num的数放在数 组的左边,大于num的数放在数组的右边。要求额外空间复杂度O(1),时间复杂度O(N)
从以下两种情况考虑
1、[i]<=num,把[i]和<=区的下一个数交换,<=区往右扩一个位置,当前数跳下一个。
2、[i]>num, i++
解:
num = 5
情况1、[i]<=num,把[i]和<=区的下一个数交换,<=区往右扩一个位置,当前数跳下一个。
定义一个数:作为<=区域的右边界
当前位置为3之前
情况1
<=【3, 5, 6, 7, 4, 3, 5, 8】当前位置为3
↓
情况1:
↓
【3】 <=【 5, 6, 7, 4, 3, 5, 8】当前位置为5
↓
情况1:
【3, 5】 <=【 6, 7, 4, 3, 5, 8】,当前数为6
↓
情况2:6>5, i++,当前数为7
↓
情况2:7>5,i++,当前数为4
↓
情况1:
4<=5,
①交换【3, 5】 <=【 4, 7, 6, 3, 5, 8】
②扩:【3, 5, 4】 <=【 7, 6, 3, 5, 8】
当前数为3
↓
情况1:
3<=5,
①交换【3, 5, 4】 <=【 3, 6, 7, 5, 8】
②扩:【3, 5, 4, 3】 <=【 6, 7, 5, 8】
当前数为5
↓
情况1:
5<=5,
①交换【3, 5, 4, 3】 <=【 5, 7, 6, 8】
②扩:【3, 5, 4, 3, 5】 <=【 7, 6, 8】
当前数为8
题目2:【<=num】【>num】不要求有序
荷兰国旗问题:荷兰国旗有三种颜色
给定一个数组arr,和一个数num,请把小于num的数放在数组的 左边,等于num的数放
在数组的中间,大于num的数放在数组的 右边。要求额外空间复杂度O(1),时间复杂度
O(N)
情况1:
变量1:<区域的右边界
变量2:>区域的左边界
1、[i] < num,把[i]和<区的下一个数交换,<区往右扩一个位置,i++跳下一个。
2、[i] = num, i++
3、[i] > num,把[i]和>区的前一个数交换,>区左扩,i原地不动(因为i是新过来的,还没看,所以不动)
i表示位置索引
当i与>区撞上时,停止。
num = 5
快速排序 快排1.0版本【3, 5, 0, 3, 4, 5, 2, 6, 9, 6】i = 3
.
【3】<【 5, 0, 3, 4, 5, 2, 6, 9, 6】i = 5
.
【3】<【 5, 0, 3, 4, 5, 2, 6, 9, 6】i = 0
.
【3】<【 0, 5, 3, 4, 5, 2, 6, 9, 6】
【3, 0】<【 5, 3, 4, 5, 2, 6, 9, 6】i = 3
.
【3, 0】<【 3, 5, 4, 5, 2, 6, 9, 6】
【3, 0, 3】<【 5, 4, 5, 2, 6, 9, 6】i = 4
.
【3, 0, 3】<【 4, 5, 5, 2, 6, 9, 6】
【3, 0, 3, 4】<【 5, 5, 2, 6, 9, 6】i=5
.
【3, 0, 3, 4】<【 5, 5, 2, 6, 9, 6】i = 2
.
【3, 0, 3, 4】<【 2, 5, 5, 6, 9, 6】
【3, 0, 3, 4, 2】<【 5, 5, 6, 9, 6】i = 6
.
【3, 0, 3, 4, 2】<【 5, 5, 6, 9, 6】
【3, 0, 3, 4, 2】<【 5, 5, 6, 9】<【 6】i = 6
.
【3, 0, 3, 4, 2】<【 5, 5, 9, 6】<【 6】
【3, 0, 3, 4, 2】<【 5, 5, 9】<【6, 6】i=9
.
【3, 0, 3, 4, 2】<【 5, 5】<【9, 6, 6】
1)把数组范围中的最后一个数作为划分值,然后把数组通过荷兰国旗问题分成三个部分:
左侧<=划分值、右侧>划分值
1)把数组范围中的最后一个数作为划分值,然后把数组通过荷兰国旗问题分成三个部分:
左侧<划分值、中间==划分值、右侧>划分值
2)对左侧范围和右侧范围,递归执行
注:总会排好一个数,所以总体最终肯定是有序的。
分析
1)划分值越靠近两侧,复杂度越高;划分值越靠近中间,复杂度越低
2)可以轻而易举的举出最差的例子,所以不改进的快速排序时间复杂度为O(N^2)。
最差情况是属于:划分值打得很偏。划分值打到几乎中点的位置是最好的情况。
随机快速排序(改进的快速排序3.0版本)划分的过程叫做partition
【4, 3, 5, 6, 5, 0, 1, 7, 8 ,5】
.
【4, 3, 0, 1】【5, 5, 5】 【 7, 8 ,6】
.
【4, 3, 0, 1】进递归:【0】【1】【4, 3】
【 7, 8 ,6】进递归:【6】【7, 8】
.
【4, 3】【7, 8】进递归:【3】【4】【7】【8】
1)在数组范围中,等概率随机选一个数作为划分值,然后把数组通过荷兰国旗问题分成三个部分:
左侧<划分值、中间==划分值、右侧>划分值
2)对左侧范围和右侧范围,递归执行
3)时间复杂度为O(N*logN)。最差情况和最好情况是概率事件,不是人为可以控制的。每种情况只占1/N的权重。数学证明太复杂,记住就行。
额外空间复杂度是O(logN)(用于记录中点位置,用递归压栈)。
等概率随机选一个位置,将其与最右侧位置的数做交换
在[L, R]范围内做partition。只返回两个值:划分值=区的左边界和右边界。
对<区做快排
对>区做快排
1)比较器的实质就是重载比较运算符(C++)
2)比较器可以很好的应用在特殊标准的排序上
3)比较器可以很好的应用在根据特殊标准排序的结构上
.sort()
.sort(reverse=True)
if(o1.id < o2.id){} :
返回-1时,o1.id放前面
返回o1.id - o2.id时,如果为正,则后者放前面;如果为负,则前者放前面,即把小的那一个放前面。o1.id放前面
Arrays.sort(数组student,比大小的方法compare())
桶排序思想下的排序1)计数排序
2)基数排序
三位数,入桶进桶3次
N位数,入桶进桶N次
分析:
1)桶排序思想下的排序都是不基于比较的排序
2)时间复杂度为O(N),额外空间负载度O(M)
3)应用范围有限,需要样本的数据状况满足桶的划分
求最大值的位
举例:



