-
2019-07-23 18:20:50
一、时间复杂度为O(n*logn)的排序算法
二、今日刷题
一、时间复杂度为O(n*longn)的排序算法
1、归并排序:
排序的思想:就是不断分成两部分:左边和右边,分别将左边和右边有序之后才进行合并得到最后的有序的数组。
时间复杂度:o(n*logn)。
核心:归并排序之所以能达到o(n*logn)的时间复杂度,主要原因是其避免了很多不必要的排序,当保持左边和右边部分有序之后,其进行合并的时候进行比较的是不同组的元素之间的比较,组内的元素不再进行比较。
代码:void merge(int a[], int l, int mid, int r) { int* help = new int[r - l + 1];//辅助数组 int p1 = l; int p2 = mid + 1; int k = 0; while (p1 <= mid&&p2 <= r) { if (a[p1] <= a[p2]) { help[k++] = a[p1]; p1++; } else { help[k++] = a[p2]; p2++; } } while (p1 <= mid) help[k++] = a[p1++]; while (p2 <= r) help[k++] = a[p2++]; int len = r - l + 1; for (int i = 0; i < len; ++i) a[l + i] = help[i]; delete[] help; //cout << "hello" << endl; } void mergesort(int a[], int l, int r) { if (l == r) return; int mid = l + ((r - l) >> 1); mergesort(a, l, mid); mergesort(a, mid + 1, r); merge(a, l, mid, r); }
例题:最小和问题和求逆序对,以最小和问题为例进行分析:
最小和问题:最小和也就是每个数的左边比其小的数的和,再将数组中所有的该和进行累加的结果,例如数组{3,5,2,6},a[0]左边没有比起小的,a[1]左边比其小的为3,a[2]左边比其小的没有,a[3]左边比其小的有3,5,2,所以数组的最小和为0+3+0+3+5+2.
分析:求最小和可以转化为求一个数的右边有多少个比其大的数,有几个那么其就贡献了几次最小和。求一个数右边有多少个比其大的使用归并排序的思想。在归并排序的merge的时候进行求解,核心思想是归并后的部分内部不必进行计算,只有不同部分之间才涉及计数;当出现相等的值的时候,先防止右边的数。
代码:
int merge(int a[], int l, int mid, int r) { int* help = new int[r - l + 1];//辅助数组 int p1 = l; int p2 = mid + 1; int k = 0; int res = 0; while (p1 <= mid&&p2 <= r) { if (a[p1] < a[p2])//左边的数字小,参与贡献 { help[k++] = a[p1]; res += (r - p2 + 1)*a[p1]; p1++; } else//左边的数字大,那么就不参与贡献 { help[k++] = a[p2]; p2++; } } while (p1 <= mid) help[k++] = a[p1++]; while (p2 <= r) help[k++] = a[p2++]; int len = r - l + 1; for (int i = 0; i < len; ++i) a[l + i] = help[i]; delete[] help; return res; //cout << "hello" << endl; } int mergesort(int a[], int l, int r) { if (l == r)//递归结束的条件,注意不要忽略 return 0; int mid = l + ((r - l) >> 1); return mergesort(a, l, mid)+mergesort(a, mid + 1, r)+merge(a, l, mid, r); //这行代码的理解个人觉得很重要 //首先将可以直接将左边家上右边再加上总体合并的,可以直接将merge(a,l,mir,r)相加的原因是 //同一个部分内部已经求解过了,也就是mergesort的部分,那么现在值涉及不同部分之间,所以直 //接加上不同部分合并的结果即可 }
2、堆排序(以大根堆为例)
堆结构其实就是一个数组,只不过将该数组视为一棵完全二叉树,对于数组中下标为i的节点,其左孩子的下标为2i+1,右孩子的下标为2i+2(数组的下标从0开始),父亲节点的下标为(i-1)/2。
堆结构中重要的操作有两个:heapinsert和headpify。heapinsert是指我们在堆中插入一个新的数字的时候,也就是在数组的末尾新增一个数字的时候将数据变成堆。
heapify是将堆顶元素删除,将剩下的数据重新变为堆。小技巧:由于数组的长度和数据的数量一般是固定的,所以我们可以使用一个单独的变量heapsize来指定堆的大小。
代码:
void heapinsert(int a[], int index)//在数组的index位置上新增加一个数 { while (a[index] > a[(index - 1) / 2])//这里已经考虑了边界条件,如果是到0,那么0和0自己比较就会跳出循环 { int tmp = a[index]; a[index] = a[(index - 1) / 2]; a[(index - 1) / 2] = tmp; index = (index - 1) / 2; } } void heapify(int a[], int index,int size) { int left = index * 2 + 1; int largest; //在进行操作之前先判断是否有左孩子和右孩子 while (left < size) { int largest = left + 1 < size&&a[left + 1] > a[left]?left + 1 : left; largest = a[largest]>a[index] ? largest : index; if (largest == index) break; int tmp = a[largest]; a[largest] = a[index]; a[index] = tmp; index = largest; left = index * 2 + 1; } }
堆排序:有了上述的操作之后,堆排序就简单了,我们使用heapinsert逐个将数组的元素加入堆,也就是不断扩大对的大小,将数组符合最大堆的情况。然后每次将堆顶取出,之后用最后的元素代替该元素,然后在heapify将剩下的又调整成最大堆,每次都得到最大值,所以最后得到的就是从大到小排好序的。
进行数组的更新:如果要进行数组的更新,那么先看看能不能heapinsert,之后看能不能headpify。
由给定数组建堆:
方法一:时间复杂度为o(nlogn),这对数组中的数据是一个一个给的或者是一次性给的都适用,具体的方法就是对每一个数组中的数字从头到尾进行heapinsert。
方法二:时间复杂度为o(logn),这只针对的是数组是一次性给定的,我们先假定给定的数组就是一个大根堆,然后对堆中的每一个位置进行heapify,也就是判断自己与其子树是否构成大根堆,那么最底层有n/2个结点,其向下的层数就是其本身,倒数第二层有n/4,其操作2层……那么总的就是n/2+n/42+n/8*3……,最后求的复杂度为o(n)。函数类库提供的堆:在C++中我们可以使用优先级队列,其就是一个堆:
//默认的就是大根堆 priority_queue<int> a; //小根堆要指明比较其 priority_queue<int,vector<int>,greater<int> > b;
例题:
题目:已知一个几乎有序的数组,几乎有序是指如果把数组排好顺序的话,每个元素移动的距离不超过k,并且k相对于数组来说比较小。请选择一个适合的排序算法针对这个数据进行排序。
思路:使用小根堆(大根堆也是可以的),首先将0到k的k+1个数进入小根堆,由于距离不超过k,所以到0位置上的数一定在这个k+1个数之间,然后在对1到k+2上的数进小根堆得到的堆顶就是1位置上的数,依次就可以得到最后有序的数组。
时间复杂度:每次调整堆的时间复杂度为o(logK),一共有n个数,所以总的时间复杂度为o(n*logK)。
代码:void sortedArrayDistanceLessK(vector<int> a, int k) { priority_queue<int, vector<int>, greater<int> > heap; int len = a.size(); //先将0到k-1的数组进堆 int index = 0; for (; index < min(len, k); index++) heap.push(a[index]); int i = 0; for (; index < len; i++, index++) { heap.push(a[index]); a[i] = heap.top(); heap.pop(); } while (!heap.empty()) { a[i++] = heap.top(); heap.pop(); } }
3、快排之partition:
快排的核心思想就是partition,而所谓partition也就是给定一个数组和一个值,将数组小于给定值的放在数组的左边,大于该值的放在数组的右边。要求时间复杂度为o(n),空间复杂度为o(1)。思路:设置一个小于等于区域,对于数组的当前的数,如果其小于等于给定的数那么其就与小于等于区域的下一个数交换,否则直接跳下一个数。从数的位置可以直观理解:数组中的数:小于等于区域---->大于区域----->当前的值。
例题:给定数组和一个值,将小于该值的放在数组的左边,等于该值的放在数组的中间,大于该值的放在数组的右边。
思路:仍然指定小于区域,等于区域和大于区域;当前的值如果小于给定的值,那么就让其与小于区域的下一个数交换,并且将当前值前进一个数;如果当前值等于给定值直接将当前值前进一个数;如果大于将当前值与大于区域的前一个值交换,当前的位置不变。从数组的位置直观理解就是:小于区域的值------>等于区域的值------->当前值------->大于区域的值。
代码:void partition(int a[], int l, int r,int label) { int less = l - 1; int more = r + 1; int tmp; while (l < more)//当当前的位置和大于区域相遇的时候结束 { if (a[l] < label) { tmp = a[l]; less++; a[l] = a[less]; a[less] = tmp; l++; } else if (a[l]>label) { tmp = a[l]; more--; a[l] = a[more]; a[more] = tmp; //当前位置不变 } else l++; } }
二、今日刷题
题目:用两个栈实现一个队列的功能
思路:队列和栈之间的区别在于,队列是先进先出,栈是后进先出。这里两个栈为s1和s2,实现队列的出队列功能:s1如果有元素的话,就将s1的元素压倒s2中,然后弹出s2栈顶的元素,如果s1是空s2有元素,那么直接弹出s2栈顶的元素;如果两个都是空的,那么报错。实现入队列,如果s2中有元素,先将s2中的元素入到s1中,然后再将新的元素push进s1中,否则直接push进s1,代码为:class Solution { //push的时候如果s2是空的,那么直接push进s1,如果s2非空,那么就要先将s2中的元素push如s1 //pop的时候,如果s2非空,那么直接pop,如果s2为空,那么将s1中的push如s2,然后再pop public: void push(int node) { int tmp; if(!s2.empty()) { tmp = s2.top(); s2.pop(); s1.push(tmp); } s1.push(node); } int pop() { int tmp; if(!s2.empty()) { tmp = s2.top(); s2.pop(); return tmp; } else if(s1.empty()) { cout<<"erroe!"; return -1; } else { while(!s1.empty()) { tmp = s1.top(); s1.pop(); s2.push(tmp); } tmp = s2.top(); s2.pop(); return tmp; } } private: stack<int> s1; stack<int> s2; };
更多相关内容 -
时间复杂度为O(N*logN)的排序算法
2019-03-13 20:25:19归并排序 这里用递归实现了归并排序,左边排序->右边排序->让其整体有序。 让其整体有序的过程中使用了排外序的方法。即构造一个新的数组,比较对i, j所指向的数字进行大小比较,如果arr[i] >...归并排序
这里用递归实现了归并排序,左边排序->右边排序->让其整体有序。
让其整体有序的过程中使用了排外序的方法。即构造一个新的数组,比较对i, j所指向的数字进行大小比较,如果arr[i] >arr[j],则将arr[i] 的值复制到新数组中,i + 1,j 不变。这样依次遍历,直到 i 或 j 到达临界点,跳出循环。将剩余部分直接拷贝到新数组中。
根据 master 公式,归并排序的时间复杂度为 O(logN * N),空间复杂度为O(N)。
归并排序的实质
代码实现:
class Sort{ public: static void merge(int arr[],int L,int mid,int R){ int i = L; int j = mid + 1; int k = 0; int *temp_arr = new int(R - L + 1); for( ; i <= mid && j <= R; ){ temp_arr[k++] = arr[i] > arr[j] ? arr[i++] : arr[j++]; } while(i <= mid){ temp_arr[k++] = arr[i++]; } while(j <= R){ temp_arr[k++] = arr[j++]; } for(i = L,k = 0; i <= R; i++,k++){ arr[i] = temp_arr[k]; } delete temp_arr; } static void mergeSort(int arr[],int L,int R){ if(L == R) return; int mid = L + ((R - L) >> 1); cout << mid << endl; mergeSort(arr,L,mid); mergeSort(arr,mid+ 1,R); merge(arr,L,mid,R); } static void mergeSort(int arr[],int length){ if(arr == NULL || length <= 0) return; mergeSort(arr,0,length - 1); } };
例题:
1. 小和问题:一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。求一个数组的小和。 例子:[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
static int merge(int arr[],int L,int mid,int R){ int i = L; int j = mid + 1; int k = 0; int res = 0; int* temp_arr = new int(R - L + 1); for( ; i <= mid && j <= R; ){ res += arr[i] < arr[j] ? arr[i] * (R - j + 1) : 0; temp_arr[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++]; } while(i <= mid){ temp_arr[k++] = arr[i++]; } while(j <= R){ temp_arr[k++] = arr[j++]; } for(i = L,k = 0; i <= R;){ arr[i++] = temp_arr[k++]; } delete temp_arr; return res; } static int mergeSort(int arr[],int L,int R) { if( L == R ) return 0; int mid = L + ((R - L) >> 1); return mergeSort(arr,L,mid) + mergeSort(arr,mid + 1,R) + merge(arr,L,mid,R); } static int smallSum(int arr[],int length){ if(arr == NULL || length == 0) return 0; return mergeSort(arr,0,length - 1); }
2.逆序对问题 在一个数组中,左边的数如果比右边的数大,则折两个数 构成一个逆序对,请打印所有逆序 对.
static int merge(int arr[],int L,int mid,int R){ int i = L; int j = mid + 1; int k = 0; int res = 0; int* temp_arr = new int(R - L + 1); for( ; i <= mid && j <= R; ){ // res += arr[i] < arr[j] ? arr[i] * (R - j + 1) : 0; // temp_arr[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++]; if(arr[i] > arr[j]){ int p = j; for( ; p <= R; p++) cout << arr[i] << " " << arr[p] << endl; temp_arr[k++] = arr[i++]; } else{ temp_arr[k++] = arr[j++]; } } while(i <= mid){ temp_arr[k++] = arr[i++]; } while(j <= R){ temp_arr[k++] = arr[j++]; } for(i = L,k = 0; i <= R;){ arr[i++] = temp_arr[k++]; } delete temp_arr; return res; } static int mergeSort(int arr[],int L,int R) { if( L == R ) return 0; int mid = L + ((R - L) >> 1); // return mergeSort(arr,L,mid) + mergeSort(arr,mid + 1,R) + merge(arr,L,mid,R); mergeSort(arr,L,mid); mergeSort(arr,mid + 1, R); merge(arr,L,mid,R); } static int inversion(int arr[],int length) { if(arr == NULL || length == 0) return 0; return mergeSort(arr,0,length - 1); }
堆
堆结构的实质是用数组实现的完全二叉树结构,可分为大根堆与小根堆。
大根堆:在完全二叉树中,每棵子树的最大值都在根节点;
小根堆:在完全二叉树中,每棵子树的最小值都在根节点。
根据完全二叉树的性质,设父节点的下标为 i ,如果它的两个孩子都存在,则左孩子的下标为 i * 2 + 1,右孩子的下标为 i*2 +2.
设子节点的下标为i,则父节点的下标为 (i - 1)/ 2.
堆结构主要包括
数据成员 heapSize:堆的大小
成员函数 heapInsert():根据一定的条件向上调节节点。O(logN)
成员函数 heapify():根据一定的条件向下调节节点。O(logN)
堆的增大与减小与数组本身的长度没有关系,只与heapSize有关。
优先级队列结构就是堆结构(小根堆)。
class HeapSort{ public: static void heapInsert(int arr[],int heapSize,int index){ while(arr[index] > arr[(index - 1) / 2]){ swap(arr[index],arr[(index - 1) / 2]); index = (index - 1) / 2; } } static void heapify(int arr[],int heapSize,int index){ int L = index * 2 + 1; while(L < heapSize){ int largest = heapSize > L + 1 && arr[L] < arr[L + 1] ? L + 1 : L; largest = arr[index] > arr[largest] ? index : largest; cout << "largest:" << largest << endl; cout << "index:" << index <<endl; if( largest == index) break; swap(arr[index],arr[largest]); index = largest; L = index * 2 + 1; } } static void addNum(int arr[],int heapSize,int new_num){ arr[heapSize++] = new_num; heapInsert(arr,heapSize,new_num); } static void altNum(int arr[],int heapSize,int index,int new_num){ arr[index] = new_num; heapInsert(arr,heapSize,index); heapify(arr,heapSize,index); } static void heapSort(int arr[],int length){ if(arr == NULL || length <= 1) return; int i = 0; for( ; i < length; i++){ heapInsert(arr,length,i); } int heapSize = length; while(heapSize > 0){ swap(arr[0],arr[--heapSize]); heapify(arr,heapSize,0); } } };
堆排序:
1. 将数组调整为大根堆
2. 将堆的最大值(根节点)与末尾的值进行交换 -> 减小heapSize -> 将数组调整为大根堆
3. heapSize = 0 排序结束
在上面的heapSort() 中,第一步将数组调整为大根堆的时间复杂度为O(N*logN),后两步的时间复杂度也是O(N*logN),所以最终堆排序的时间复杂度为O(N*logN).
实际上heapSort()中,第一步还可以继续优化,上面采用的是自顶向下的建堆方式,优化的算法采用的是自底向上的建堆方式,即从(heapSize - 1)开始,依次倒序遍历数组,同时执行heapigy()函数,知道heapSize = 0。该算法的时间复杂度为O(N),证明如下:
若存在一个节点个数为N的完全二叉树,则最底层的节点个数为N / 2, 倒数第二层的节点个数为 N / 4......,
所以 该算法的常数时间的操作为 T(N) = N / 2 + N / 4 * 2 + N / 8 * 3 + ......
而 2T(N) = N / 2 * 2 + N / 2 * 2 + N / 4 * 3 + ......
所以 T(N) = N + N / 2 + N / 4 + ...... = N * (1 - 1 / 2) / (1 - 1 / 2) = N * ( 1 / 2) ^ (N - 1)
所以使用该种方法建立大根堆的时间复杂度为O(N).
在排序过程中,将数组调整为大根堆共有两种方式:
自顶向下的建堆:依次读入数组的值,将值看作新加入堆的值,然后使用heapInsert() 函数向上调节节点到它应该在位置,时间复杂度为O(N*logN);
自底向下的建堆:时间复杂度为O(N)。
堆排序扩展题目
1. 已知一个几乎有序的数组,几乎有序是指,如果把数组排好顺序的话,每个元 素移动的距离可以不超过k,并且k相对于数组来说比较小。请选择一个合适的 排序算法针对这个数据进行排序。
解题思路:首先建立一个小根堆,将前k + 1个数加入小根堆,从小根堆中选出最小的数放在0位置;再将第k+ 2个数放入小根堆,将现在小根堆中最小的数放在1位置。。。。。。该算法的时间复杂度为O(N*logk)。
注:可以使用priority_queue来简化。
public void sortedArrDistanceLessK(int[] arr, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(); int index = 0; for (; index < Math.min(arr.length, k); index++) { heap.add(arr[index]); } int i = 0; for (; index < arr.length; i++, index++) { heap.add(arr[index]); arr[i] = heap.poll(); } while (!heap.isEmpty()) { arr[i++] = heap.poll(); } }
快速排序
首先介绍荷兰国旗问题
问题一
给定一个数组arr,和一个数num,请把小于等于num的数放在数 组的左边,大于num的 数放在数组的右边。要求额外空间复杂度O(1),时间复杂度O(N)
问题二给定一个数组arr,和一个数num,请把小于num的数放在数组的 左边,等于num的数放 在数组的中间,大于num的数放在数组的 右边。要求额外空间复杂度O(1),时间复杂度 O(N)
解决荷兰国旗问题的思路是:分别定义 less 和 more 来划分大于num与小于num在数组中的范围,用index来遍历数组,初始时 less = -1,more = arr.length,index = 0。
1. 如果arr[index] > num,more--,交换arr[more] 与arr[index];
2. 如果arr[index] < num,less++,index++;
3. 如果arr[index] = num,,index++.
public static int[] partition(int[] arr, int l, int r, int p) { int less = l - 1; int more = r + 1; while (l < more) { if (arr[l] < p) { swap(arr, ++less, l++); } else if (arr[l] > p) { swap(arr, --more, l); } else { l++; } } return new int[] { less + 1, more - 1 }; }
荷兰国旗问题的算法实现就是快速排序中最重要的部分。
经典快排的实现过程:
1. 将arr[length - 1] 作为划分值,然后通过荷兰国旗问题把数组划分为3个部分:左侧< 划分值;右侧 > 划分值;中间= 划分值。
2. 将arr[length - 1] 的值与arr[index] > 划分值的前一个数做交换。
3. 令index = 划分值的位置 - 1,递归执行上述过程;令index = 划分值的位置+1,递归执行上述过程。
经典快排的时间复杂度为O(N^2);
对这个算法可以做出改进。
改进一:
与经典快排的实现过程基本相同,但在做完交换后进行,令index = less,递归;index = more,递归。
在最差情况下,该算法的时间复杂度同样为O(N^2).
划分值越接近两侧,时间复杂度越高;划分值越接近中间,划分值越低。
在最好的情况下,该算法的时间复杂度为O(N);
改进二:
1)在数组范围中,等概率随机选一个数作为划分值,然后把数组通过荷兰国旗问题分 成三个部分: 左侧<划分值、中间==划分值、右侧>划分值
2)对左侧范围和右侧范围,递归执行
3)时间复杂度为O(N*logN)
在这种情况下,取到任何划分值的可能性都是随机且相等的。最好情况下的时间复杂度为O(N* logN),最差情况下为O(N^2),经过复杂的数学推演(真的很复杂,都看不懂),时间复杂度可以收敛为O(N*logN).
对于空间复杂度,最差情况下为O(N),最好情况下为O(logN),收敛后为O(logN).
class Sort{ public: static void quickSort(int arr[],int length){ if(arr == NULL || length <= 1){ return; } quickSort(arr,0,length - 1); } static void quickSort(int arr[],int L,int R) { if(L == R) return; int temp = arr[rand()%(R - L + 1)]; int num = arr[temp]; int less = L - 1; int more = R; int i = L; for(; i < more;){ if(arr[i] < num){ swap(arr[++less],arr[i++]); } else if(arr[i] > num){ swap(arr[--more],arr[i]); } else{ i++; } } swap(arr[temp],arr[less + 1]); quickSort(arr,0,less); quickSort(arr,more,R); } };
-
基础算法-2: 时间复杂度为O(N*logN)的排序算法
2020-01-31 21:38:47时间复杂度 O(N*logN): 归并排序,堆排序(大根堆,小根堆,heapInsert/heapify),快速排序(荷兰国旗问题)。 归并排序 L — Mid — R 先让 左有序,右有序。 归并 谁小copy谁 def mergeSort(data): def ...时间复杂度 O(N*logN):
归并排序,堆排序(大根堆,小根堆,heapInsert/heapify),快速排序(荷兰国旗问题)。- 归并排序
L — Mid — R
先让 左有序,右有序。
归并 谁小copy谁
def mergeSort(data): def mergeSortFunc(data, L, R): if L==R: return mid = L+(R-L)//2 mergeSortFunc(data, L, mid) //左部分 merge sort mergeSortFunc(data, mid+1, R)//右部分 merge sort merge(data, L, R, mid) // 左右 merge def merge(data, L, R, M): help_arr = [] p1 = L p2 = M+1 while p1<=M and p2<=R: if data[p1] <= data[p2]: help_arr.append(data[p1]) p1++ else: help_arr.append(data[p2]) p2++ while p1<=M: help_arr.extend(data[p1:M+1]) while p2<R: help_arr.extend(data[p2:R+1]) data[L:R+1] = help_arr if len(data) < 2: return mergeSortFunc(data, 0, len(data)-1)
T(N) = 2T(N/2) +O(N) 所以 时间复杂度就是 O(N*logN), 额外空间复杂度是 O(N)
题目:小和问题 和 逆序对问题
小和问题:在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和,求一个数组的小和。
//解法: 暴利查询 每个数查询左侧比他小的值 并且求和, 时间复杂度O(N^2) //解法2: 归并。 一个数a 左边比他小的数加和 产生小和 与 右边有多少个比他大产生 n*a 小和 等价. ''' 例: 1 3 4 2 5 划分左右 1 3 4 2 5 划分左右 1 3 4 2 5 merge 时 右侧比 左侧大的时候 产生小和。 1 3 merge:1<3 , 右侧有1个比1 大。所以 1* 1 13 4 merge: 1<4,右侧有1个比1大, 产生1*1, 3和4比较, 3<4,右侧有1个比3大,产生1*3. 得到 1 3 4 2 5 merge: 2 < 5, 右侧有1个比2大,所以产生1*2 得到2 5 134 25 merge: --> 1 < 2: 右侧有2个比1大, 产生2*1. 新的数组得到 1. 原数组为 34 25 --> 3 > 2: 不产生小和。新的数组为 1 2,原数组为 34 5 --> 3 < 5: 右侧有1个比3大, 产生1*3. 新数组得到 1 2 3, 原数组为4 5 --> 4 < 5: 右侧有1个比4大, 产生1*4. 新数组为 1 2 3 4 5. 最后产生的小和: 1*1 + 1*1 + 1*3 + 1*2 + 2*1 + 1*3 + 1*4 = 16 merge 实质:让左侧的数 依次碰到每一个右侧的数。 每一次搞定的左侧 不需要重复求,并且计算右侧有多少个比当前数大的时候 可以通过下标直接计算得到 不需要一个个数,因为左侧和右侧都是有序的,当左侧小于右侧的时候 产生小和。 merge sort 好的地方在于 每次比较结果都是变成有序序列。后续比较 只需要左组 和右组进行比较,不需要组内比较, 只需要跨组比较。 暴利查询:1: 左侧小于1的 无。 3: 左侧小于3的 1, 4: 左侧小于4的1,3, 2: 左侧小于2的1 5: 左侧小于5的1,2,3,4 加和: 1+1+3+1+1+2+3+4 = 16 ''' def leastSum(data): def mergeSort(data, L, R): if L==R: return 0 mid = L+(R-L)//2 return mergeSort(data, L, mid) + mergeSort(data, mid+1, R) + mergeAndSum(data, L, R, mid) def mergeAndSum(data, L, R, Mid): p1 = L p2 = Mid+1 help_arr = [] ret = 0 while p1 <= Mid and p2 <= R: if data[p1]< data[p2]: help_arr.append(data[p1]) ret += (R-p2+1)*data[p1] p1++ else data[p1]>=data[p2]://相等的时候 copy 右部分。 help_arr.append(data[p2]) p2++ while p1<=Mid: help_arr.extend(data[p1:Mid+1]) while p2<=R: help_arr.extend(data[p2:R+1]) data[L:R+1] = help_arr return ret //leastSum func if len(data)<2: return return mergeSort(data, 0, len(data)-1, ret)
逆序对:在一个数组中,左边的数如果比右边的数大,则这两个数构成一个逆序对,请打印所有的逆序对。(即求每个数 左边多少个比它大的数)
def reverseData(data): if len(data)< 2: return def mergeSort
-
堆
堆:用数组实现的完全二叉树结构(默认下标从0开始)
0 1 2 3 4 5 6 7
–> 0
1 2
3 4 5 6
完全二叉树: 结点i, 父节点 (i-1)/2 左孩子: 2i +1, 右孩子: 2i+2大根堆:对于每颗子树的最大值 就是 父节点
小根堆:对于每颗子树的最小值 就是父节点heapsize 是堆的一个重要参数。
任何一个数组 都可以按照大根堆的方式进行排序。 时间复杂度为O(Log_2 N)
def heapInsert(data, index): //数字 来到了 index 位置,如何往上移动 while data[index] > data[(index-1)//2]: data[index], data[(index-1)//2] = data[(index-1)//2],data[index] index = (index-1)//2 // 即包含了index在0位置 没有父节点的时候 也包含 index在其他位置 有父节点的时候 // index = 0 时, (index-1)//2 也等于0
如果用户跟我要数的时候,比如要大根堆的堆顶,但是剩下的还是希望是大根堆结构。如何做?
用最后一个位置填堆顶,heapsize 减1,相当于把最后一个位置在堆里面移除。此时需要调整为大根堆,也就是把堆顶往下调整。时间复杂度为O(Log_2 N)
def heapify(data, index, heapSize): left = index * 2 + 1 //左孩子下标 while left < heapSize: //下方还有孩子的时候 if left+1 < heapSize and data[left+1] > data[left]: largest = left+1 else: largest = left if data[largest] < data[index]: largest = index break data[largest], data[index] = data[index], data[largest] index = largest left = index*2 + 1
如果某个位置的值发生了变化,则可以heapInsert 和heapify 各来一遍,最多只可能发生一个函数操作。
-
堆排序
给定一个数组,先把数组整体变成大根堆,此时heapsize=N。
比如: 9 8 3 7 6 2 1
step-1: 建立大根堆
step-2:把堆顶 和最后一个位置交换。把最后一个位置去掉。heapSize-1
step-3: 调整当前的数组为大根堆。如果数组放那边,调整成大根堆 可以自顶往上(时间复杂度为O(logN)),也可以自底往上(时间复杂度度O(N))。
自底往上把数组调整成大根堆。一开始认为数组为一个完全二叉树,从最后一个数开始 调整为大根堆(看他是否比每一个子孩子大,如果是的话 就往下走)heapify堆排序:时间复杂度为O(NlogN), 额外空间复杂度O(1)
//从顶往下 def heapSort(data): if len(data)<2: return for i in range(0, len(data)): heapInsert(data[i],i) heapSize = len(data)-1 data[0],data[heapSize] = data[heapSize],data[0] while heapSize>0: heapify(data,0,heapSize) data[0],data[heapSize] = data[heapSize],data[0]
-
堆扩展
已知一个几乎有序的数组,几乎有序是指的是 如果把数组排好顺序的话,每个元素一定的距离可以不超过K, 并且K相对于数组来说比较小。请选择一个合适的排序算法针对这个数组排序。
答: 使用堆。 为什么?如何用?
先把0-(K+1)个数 设置为小根堆,也就是0位置放最小的。
然后再把1-(K+2)个数 设置为小根堆,得到1的位置。
。。。
时间复杂度O(N * log K) (小根堆调整是log K 级别的) -
快速排序
5-1:快排的partition的思想
问题1: 给定一个数a,和数组A,请先做到 把小于等于a的放到左边,大于a的放到右边。要求时间复杂度O(N),额外空间复杂度O(1)。
方法:
设一个小于等于 区域。最开始为空。
当前数 <= a, 当前数和小于等于区域下一个数 交换,然后小于等于区域阔一个位置,当前数跳到下一个。
当前数 >a, 当前数直接跳下一个。
需要有的参数:小于等于区域指针,当前数指针。问题1拓展:荷兰国旗问题。小于a的放到左边,等于a放中间,大于a的放右边。
方法:
当前数=划分值, 当前数跳到下一个
当前数<划分值,当前数 与小于区域 下一个数 交换,小于区域 往后扩一个,当前数跳到下一个
当前数>划分值,当前数与大于区域 前一个数 交换,大于区域往前扩一个,当前不变。
当前数与大于区域撞上时,停止。小于划分值区域 等于区域 当前数 …(待定区域) 大于区域
def NetherLandsFlag(data,p): def partition(data, L, R, p):// p是划分值,要把L-R区间调整 less = L-1 //小于区域的右边界 more = R + 1//大于区域的左边界 while L< more: // L是当前数下标 if data[L] < p://小于划分值 data[L], data[less+1] = data[less+1], data[L]//交换 less++ L++ else if data[L]> p: data[L], data[more-1] = data[more-1], data[L] more-- else: L++ return [less+1, more-1] //等于区域的下标 if len(data)<1: return partition(data, 0, len(data)-1, p)
5-2:快排
不改进的快速排序:
1) 把数组范围中的最后一个数作为划分值,然后把数组通过荷兰国旗问题分成3个部分:左侧<划分值,中间==划分值,右侧>划分值。
2)对左侧范围和右侧范围,递归执行。分析:
1)划分值越靠近两侧,复杂度越高,划分值越靠近中间,复杂度越低.
2)可以轻而易举地举出最差的例子,所以不改进的快排时间复杂度是O(N^2) (比如:1,2,3,4,5,6 划分值是6)。最好的情况是partition 的位置几乎在中点,时间复杂度O(NlogN)。
3)为了防止每次都是最差的情况出现,则通过L-R上随机选择一个数和N-1位置交换,这样降低复杂度。 (因为随机选择一个数,所以各种情况都是均等的,最后平均复杂度为O(NlogN))经典快排:
(L-R上随机选一个数字和N-1位置上的数进行交换)X 在N-1位置上,对0-N-2上的数进行partition <=x, >x (<=x 左侧,>x 右侧,然后把x和>x区域的第一个数交换),保证小于等于区域最后一个数是x.这样对于<=区域继续递归,然后对>x区域递归。 Base case: 区域只有一个值时 不需要排序。
(最差的情况 时间复杂度O(N^2),空间复杂的O(N),最好的情况是时间复杂度O(N*logN),空间复杂度O(logN))改进的快排:
(L-R上随机选一个数字和N-1位置上的数进行交换)X是N-1上的划分值,在0 - (N-2)上进行荷兰国旗加速 <x, =x, >x(得到3个区域),然后把X和大于区域第一个值交换,并且大于区域往后移一位。然后在<x 和>x 区域分别做递归.改进VS 经典快排:
改进的快排是每次排序 可以把所有等于x的都搞定 ,而经典的快排是每次都只能搞定一个数(也就是只有最后那个划分值 放到正确的位置)def quickSort(data): def partition(data, L, R):// less = L-1 more = R // 最后一个作为划分值 while L < more: if data[L] < data[R]: data[L], data[less+1] = data[less+1],data[L] L++ less++ else if data[L] > data[R]: data[L], data[more-1] = data[more-1],data[L] more-- else: L++ data[more-1], data[R] = data[R],data[more-1] return (less+1, more) def q_sort(data, L, R)://排好L-R之间的数 if L<R: index = random(L, R) data[R], data[index] = data[index], data[R] p = partition(data, L, R) q_sort(data, L, p[0]-1) q_sort(data, p[1]+1, R) if len(data)<2: return q_sort(data, 0, len(data)-1)
- 归并排序
-
时间复杂度为O(logn)的算法
2018-04-23 19:21:27今天被问到了关于时间复杂度的问题,关于O(logn)我还真有点懵,所以找了篇博客学习记录一下。 下面内容转载自https://blog.csdn.net/u011619283/article/details/51878201 典型时间复杂度 我们知道算法的执行...今天被问到了关于时间复杂度的问题,关于O(logn)我还真有点懵,所以找了篇博客学习记录一下。
下面内容转载自https://blog.csdn.net/u011619283/article/details/51878201典型时间复杂度
我们知道算法的执行效率,可以从它的时间复杂度来推算出一二。而典型的时间复杂度有哪些类型呢?
由上图,可以看出,除了常数时间复杂度外,logN型的算法效率是最高的。今天就介绍三种非常easy的logN型算法。对分查找
给定一个整数X和整数A0,A1,…,An-1,后者已经预先排序并在内存中,求是的Ai= X的下表i,如果X不在数据中,则返回i = -1.
- (int)BinarySearch:(NSArray *)originArray element:(int)element { int low, mid, high; low = 0; high = (int)originArray.count - 1; while (low <= high) { mid = (low + high) / 2; if ([originArray[mid] intValue] < element) { low = mid + 1; } else if ([originArray[mid] intValue] > element) { high = mid -1; } else { return mid; } } return -1; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
* 分析 :*通过上面的程序可以看出,要算出时间复杂度,就是求出while循环的次数。
mid 每次的取值分别是数组长度(N-1)/2,(N-1)/2/2,(N-1)/2/2/2,…,1,0,-1。那么只用求出2的多少次方等于N-1,再加上可能的多需要的次数2。假设2的f次方等于N-1,最大时间即为log(N-1) + 2。因此对分查找的时间复杂度为logN。再举一个实际的例子,假设最初high = 128,low = 0,则mid的最大取值为64,32,16,8,4,2,1,0,-1。大家可以计算时间。欧几里得算法
第二个是计算最大公因数的欧几里得算法。两个整数的最大公因数Gcd是同时整除二者的最大整数。于是,Gcd(50,15) = 5。
- (unsigned int)Gcd:(unsigned int)m n:(unsigned int)n { unsigned int Rem; while (n > 0) { Rem = m % n; m = n; n = Rem; } return m; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
算法超级简单,但是里面还是有一些精髓的。算法假设m>=n,但是如果m < n,则在第一次while循环后,m和n 会互相交换。
该算法的整个运行时间依赖于确定余数序列的长度,也就是while循环的次数。
依然举例m = 1989 和n = 1590,则余数序列是399,393,6,3,0。从而,Gcd(1989,1590) = 3。
虽然看不出余数的值是按照常数引子递减,有时候递减的非常少,例如从399递减到393。但是,我们可以证明,两次迭代以后,余数最多是原始值的一半。迭代次数至多是2logN,所以时间复杂度是logN。
怎么证明 M > N,则M mod N < M /2呢?
如果N =< M/2,则由于余数小于N,即M mod N < N <= M/2,所以余数也小于M/2。
如果N> M/2,则此时M中有个N,从而余数M-N < M/2。幂运算
最后一个算法,是计算一个整数的幂。我们可以用乘法的次数作为运行时间的度量。
计算X的N次方常见的算法是使用N-1次乘法自乘。但是用递归算法更好。- (long)Pow:(long)x n:(unsigned int)n { if (n == 0) { return 1; } if (n == 1) { return x; } if ([self isEven:n]) { return [self Pow:x * x n:n / 2]; } else { return [self Pow:x * x n:n / 2] * x; } } - (BOOL)isEven:(unsigned int)n { if (n % 2 == 0) { return YES; } else { return NO; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
如果N是偶数,则X的N次方 = X的N/2次方乘以X的N/2次方,如果N是奇数,则X的N次方 = X 的(N-1)/2 次方乘以 X的(N-1)/2次方乘以X。
显然,所需要的乘法次数最多是2logN。那么时间复杂度就是logN咯。 -
时间复杂度为O(N*logN)的常用排序算法总结与Java实现
2018-03-26 17:53:32时间复杂度为O(N*logN)的常用排序算法主要有四个——快速排序、归并排序、堆排序、希尔排序1.快速排序·基本思想 随机的在待排序数组arr中选取一个元素作为标记记为arr[index](有时也直接选择起始位置),然后在arr... -
各种排序算法的时间复杂度对比
2020-07-26 18:32:21各种排序算法的时间复杂度对比 -
常见排序算法的时间复杂度、空间复杂度、稳定性比较
2019-09-17 19:59:08常见排序算法的时间空间复杂度、稳定性比较 一、排序算法比较 注: 1、归并排序可以通过手摇算法将空间复杂度降到O(1),但是时间复杂度会提高。 2、 基数排序时间复杂度为O(N*M),其中N为数据个数,M为数据位数... -
算法复杂度O(logn)详解
2021-05-22 03:05:26//时间复杂度为O(1)的程序步骤序列}由于cnt每次在乘以2之后都会更加逼近n,也就是说,在有x次后,cnt将会大于n从而跳出循环,所以\(2 ^ x = n\), 也就是\(x = log_2n\),所以这个循环的复杂度为O(logn)二.典型时间... -
每日一道算法(搜索插入位置——二分查找,时间复杂度为O(logn) )
2022-01-14 10:25:20算法时间复杂度的时候有说o(1), o(n), o(logn), o(nlogn),这是算法的时空复杂度的表示。不仅仅用于表示时间复杂度,也用于表示空间复杂度。O后面的括号中有一个函数,指明某个算法的耗时/耗空间与数据增长量之间的... -
算法(一)——时间复杂度及常用排序算法时间复杂度
2019-07-13 20:19:14算法效率度量 1.时间复杂度O(n) 原则: 常数1代替所有加法中的常数 只保留最高阶数项(且不要前面的系数) ...O(n logn)<...2.空间复杂度 ...常用空间换时间 ...时间复杂度 ...时间复杂度:算法性能指标...常用排序算法及... -
各种排序算法的时间复杂度
2019-06-04 13:06:31当我们评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度,在算法分析时,经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度,其中的f(n)一般是算法中频度最大的语句频度。算法中语句的频度不仅与... -
排序算法 时间复杂度+空间复杂度 总结
2022-02-15 23:48:24排序算法 时间复杂度+空间复杂度 总结 -
排序算法时间复杂度、空间复杂度、稳定性比较
2017-07-30 21:33:22排序算法分类排序算法比较表格填空 排序算法 平均时间复杂度 最坏时间复杂度 空间复杂度 是否稳定 冒泡排序 :————-: :—–: :—–: :—–: 选择排序 :————-: :—–: :—–: :—–: 直接插入... -
排序—时间复杂度为O(nlogn)的两种排序算法
2020-12-24 13:52:33上一个排序随笔中分析了三种时间复杂度为O(n2)的排序算法,它们适合小规模数据的排序;这次我们试着分析时间复杂为O(nlogn)的排序算法,它们比较适合大规模的数据排序。1 归并排序1.1 原理将待排序列划分为前后两... -
排序算法 - 时间复杂度O(N*logN)的归并、快速排序算法
2021-03-02 14:04:27归并排序、快速排序都使用了分治的思想,时间复杂度都是O(N*logN)。由于其时间复杂度低,所以被广泛的应用,比如Java Collection.sort; Mysql数据库中的排序;Tim排序等。 -
常见排序算法及其时间复杂度
2019-06-20 18:00:18常见排序算法及其时间复杂度 一、内部排序:1.稳定的排序算法1.1 冒泡排序1.1.1 冒泡排序流程1.1.2 冒泡排序的实现1.2 插入排序1.2.1 插入排序流程1.2.2 插入排序的实现1.3 归并排序1.3.1 归并排序流程1.3.2 归并... -
常见排序算法及其时间复杂度(超详细)
2019-09-19 23:15:44稳定的排序算法 稳定的排序 时间复杂度 空间复杂度 冒泡排序(bubble sort) 最差、平均都是O(n^2),最好是O(n) 1 插入排序(insertion sort) 最差、平均都是O(n^2),最好是O(n) 1 归并排序(merge sort) 最差、平均、... -
冒泡和快速排序的时间复杂度_java 八大排序算法 冒泡排序 快速排序 堆排序 归并排序 等...
2020-11-22 10:05:36八大排序算法一、直接插入1.基本思路在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。2.代码... -
排序算法-归并排序的时间复杂度分析
2019-08-23 14:26:56归并排序,其实就是递归+合并。 -
常见排序算法及其对应的时间复杂度和空间复杂度
2020-09-10 01:56:37排序算法经过长时间演变,大体可以分为两类:内排序和外排序。在排序过程中,全部记录存放在内存,则成为内排序;如果排序过程中需要使用外存,则称为外排序,本文讲的都属于内排序。 内排序有可以分为以下几类: ... -
常用的排序算法的时间复杂度和空间复杂度
2019-10-30 14:52:51描述算法复杂度时,经常用到o(1), o(n), o(logn), o(nlogn)来表示对应算法的时间复杂度, 它们代表的含义: 这是算法的时空复杂度的表示。不仅仅用于表示时间复杂度,也用于表示空间复杂度。大O加上()的形式,里面... -
排序算法之 归并排序及时间复杂度分析
2020-05-12 20:13:53排序算法之 冒泡排序及性能优化(时间复杂度+空间复杂度分析) 排序算法之 简单选择排序及时间复杂度分析 排序算法之 直接插入排序及时间复杂度分析 排序算法之 希尔排序及时间复杂度分析 排序算法之 快速排序及时间... -
前端常用算法----时间复杂度为O(nlogN)的排序算法
2020-10-31 17:08:02时间维度:是指执行当前算法所花费的时间,我们通常用「时间复杂度」来描述。 空间复杂度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。 时间维度 O(n) for(var i = 0; i < n;... -
排序算法时间复杂度比较
2019-01-27 08:53:46各种排序算法比较 一、基本排序算法 冒泡排序 假如我们现在按身高升序排队,一种排队的方法是:从第一名开始,让两人相互比身高,若前者高则交换位置,更高的那个在与剩下的人比,这样一趟下来之后最高的人就站到... -
二分查找O(logn)和归并排序O(nlogn)时间复杂度介绍
2022-03-22 09:48:47本文通过二分查找和并归排序为例,主要介绍时间O(logn)和O(nlogn)这两个时间复杂度是怎么得出来的。O(1)、O(n)、O(n2)在此不做介绍了,O(n)、O(n2)就是for循环一次、二次,O(1)的话…就好像单例模式或者map吧。 首先... -
常见排序算法的最好、最坏、平均时间复杂度、稳定性、是否基于比较
2020-07-10 17:35:39时间复杂度 空间复杂度 稳定性 关联性 最好 最差 平均  ... -
排序算法时间复杂度函数图像
2019-09-21 04:15:47这是使用desmos画出来的图形。...)低于xlog(x)高于x,但通常我们的排序算法快排和归并的最优是xlog(x)最坏是n^2, 通过二分查找改进的排序算法最坏是log(n!),最好是n。 虽然nlog(n)和log(n!)相差不... -
C/C++中四种排序算法的时间空间复杂度
2020-08-11 13:36:15C/C++中四种排序算法的时间空间复杂度 一.浅谈时间复杂度和空间复杂度 1.概念: 时间复杂度:就是说执行算法需要消耗的时间长短,越快越好。 空间复杂度:就是说执行当前算法需要消耗的存储空间大小,也是越少越好。... -
排序算法之 快速排序 及其时间复杂度和空间复杂度
2017-09-14 10:13:19快速排序是排序算法中效率相对较高的,但使用的人却是比较少,大家一般信手拈来的排序算法就是冒泡排序。因为冒泡排序主观,容易理解,而快速排序使用到了递归,大家可能就有点不知所措了。 算法分析 快速...