精华内容
下载资源
问答
  • topk排序
    千次阅读
    2020-06-13 11:44:17

    目录

    1.介绍1

    2.介绍2

    3.介绍3 包括各种排序的空间及时间复杂度


    1.介绍1

    摘自 https://www.cnblogs.com/itxiaok/archive/2019/02/15/10385676.html

    前两天面试3面学长问我的这个问题(想说TEG的3个面试学长都是好和蔼,希望能完成最后一面,各方面原因造成我无比想去鹅场的心已经按捺不住了),这个问题还是建立最小堆比较好一些。

        先拿10000个数建堆,然后一次添加剩余元素,如果大于堆顶的数(10000中最小的),将这个数替换堆顶,并调整结构使之仍然是一个最小堆,这样,遍历完后,堆中的10000个数就是所需的最大的10000个。建堆时间复杂度是O(mlogm),算法的时间复杂度为O(nmlogm)(n为10亿,m为10000)。
    ​
        优化的方法:可以把所有10亿个数据分组存放,比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数,合并到一起在再找出最终的结果。
    ​
        以上就是面试时简单提到的内容,下面整理一下这方面的问题:

    top K问题 在大规模数据处理中,经常会遇到的一类问题:在海量数据中找出出现频率最好的前k个数,或者从海量数据中找出最大的前k个数,这类问题通常被称为top K问题。例如,在搜索引擎中,统计搜索最热门的10个查询词;在歌曲库中统计下载最高的前10首歌等。 针对top K类问题,通常比较好的方案是分治+Trie树/hash+小顶堆(就是上面提到的最小堆),即先将数据集按照Hash方法分解成多个小数据集,然后使用Trie树活着Hash统计每个小数据集中的query词频,之后用小顶堆求出每个数据集中出现频率最高的前K个数,最后在所有top K中求出最终的top K。

    eg:有1亿个浮点数,如果找出期中最大的10000个? 最容易想到的方法是将数据全部排序,然后在排序后的集合中进行查找,最快的排序算法的时间复杂度一般为O(nlogn),如快速排序。但是在32位的机器上,每个float类型占4个字节,1亿个浮点数就要占用400MB的存储空间,对于一些可用内存小于400M的计算机而言,很显然是不能一次将全部数据读入内存进行排序的。其实即使内存能够满足要求(我机器内存都是8GB),该方法也并不高效,因为题目的目的是寻找出最大的10000个数即可,而排序却是将所有的元素都排序了,做了很多的无用功

    第二种方法为局部淘汰法,该方法与排序方法类似,用一个容器保存前10000个数,然后将剩余的所有数字——与容器内的最小数字相比,如果所有后续的元素都比容器内的10000个数还,那么容器内这个10000个数就是最大10000个数。如果某一后续元素比容器内最小数字,则删掉容器内最小元素,并将该元素插入容器,最后遍历完这1亿个数,得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为O(n+m^2),其中m为容器的大小,即10000。

    第三种方法是分治法,将1亿个数据分成100份,每份100万个数据,找到每份数据中最大的10000个,最后在剩下的10010000个数据里面找出最大的10000个。如果100万数据选择足够理想,那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下:用快速排序的方法,将数据分为2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大堆个数N小于10000个,就在小的那堆里面快速排序一次,找第10000-n大的数字;递归以上过程,就可以找到第1w大的数。参考上面的找出第1w大数字,就可以类似的方法找到前10000大数字了。此种方法需要每次的内存空间为10^64=4MB,一共需要101次这样的比较。

    第四种方法是Hash法。如果这1亿个书里面有很多重复的数,先通过Hash法,把这1亿个数字去重复,这样如果重复率很高的话,会减少很大的内存用量,从而缩小运算空间,然后通过分治法或最小堆法查找最大的10000个数。

    第五种方法采用最小堆。首先读入前10000个数来创建大小为10000的最小堆,建堆的时间复杂度为O(mlogm)(m为数组的大小即为10000),然后遍历后续的数字,并于堆顶(最小)数字进行比较。如果比最小的数小,则继续读取后续数字;如果比堆顶数字大,则替换堆顶元素并重新调整堆为最小堆。整个过程直至1亿个数全部遍历完为止。然后按照中序遍历的方式输出当前堆中的所有10000个数字。该算法的时间复杂度为O(nmlogm),空间复杂度是10000(常数)。

    实际运行: 实际上,最优的解决方案应该是最符合实际设计需求的方案,在时间应用中,可能有足够大的内存,那么直接将数据扔到内存中一次性处理即可,也可能机器有多个核,这样可以采用多线程处理整个数据集。

     

    2.介绍2

    摘自 https://blog.csdn.net/wufaliang003/article/details/82940218

    TopK,是问得比较多的几个问题之一,到底有几种方法,这些方案里蕴含的优化思路究竟是怎么样的,今天和大家聊一聊。

    问题描述:

    从arr[1, n]这n个数中,找出最大的k个数,这就是经典的TopK问题。

    栗子:

    从arr[1, 12]={5,3,7,1,8,2,9,4,7,2,6,6} 这n=12个数中,找出最大的k=5个。

     

    一、排序

     

    排序是最容易想到的方法,将n个数排序之后,取出最大的k个,即为所得。

     

    伪代码:

    sort(arr, 1, n);

    return arr[1, k];

     

    时间复杂度:O(n*lg(n))
     

    分析:明明只需要TopK,却将全局都排序了,这也是这个方法复杂度非常高的原因。那能不能不全局排序,而只局部排序呢?这就引出了第二个优化方法。

     

    二、局部排序

    不再全局排序,只对最大的k个排序。

     

    冒泡是一个很常见的排序方法,每冒一个泡,找出最大值,冒k个泡,就得到TopK。

     

    伪代码:

    for(i=1 to k){

             bubble_find_max(arr,i);

    }

    return arr[1, k];

     

    时间复杂度:O(n*k)

     

    分析:冒泡,将全局排序优化为了局部排序,非TopK的元素是不需要排序的,节省了计算资源。不少朋友会想到,需求是TopK,是不是这最大的k个元素也不需要排序呢?这就引出了第三个优化方法。

     

    三、堆

    思路:只找到TopK,不排序TopK。

     

    先用前k个元素生成一个小顶堆,这个小顶堆用于存储,当前最大的k个元素。

     

     

    接着,从第k+1个元素开始扫描,和堆顶(堆中最小的元素)比较,如果被扫描的元素大于堆顶,则替换堆顶的元素,并调整堆,以保证堆内的k个元素,总是当前最大的k个元素。

     

     

    直到,扫描完所有n-k个元素,最终堆中的k个元素,就是猥琐求的TopK。

     

    伪代码:

    heap[k] = make_heap(arr[1, k]);

    for(i=k+1 to n){

             adjust_heap(heep[k],arr[i]);

    }

    return heap[k];

     

    时间复杂度:O(n*lg(k))

    画外音:n个元素扫一遍,假设运气很差,每次都入堆调整,调整时间复杂度为堆的高度,即lg(k),故整体时间复杂度是n*lg(k)。

     

    分析:堆,将冒泡的TopK排序优化为了TopK不排序,节省了计算资源。堆,是求TopK的经典算法,那还有没有更快的方案呢?

     

    四、随机选择

    随机选择算在是《算法导论》中一个经典的算法,其时间复杂度为O(n),是一个线性复杂度的方法。

     

    这个方法并不是所有同学都知道,为了将算法讲透,先聊一些前序知识,一个所有程序员都应该烂熟于胸的经典算法:快速排序。

    画外音:

    (1)如果有朋友说,“不知道快速排序,也不妨碍我写业务代码呀”…额...

    (2)除非校招,我在面试过程中从不问快速排序,默认所有工程师都知道;

     

    其伪代码是:

    void quick_sort(int[]arr, int low, inthigh){

             if(low== high) return;

             int i = partition(arr, low, high);

             quick_sort(arr, low, i-1);

             quick_sort(arr, i+1, high);

    }

     

    其核心算法思想是,分治法。

     

    分治法(Divide&Conquer),把一个大的问题,转化为若干个子问题(Divide),每个子问题“都”解决,大的问题便随之解决(Conquer)。这里的关键词是“都”。从伪代码里可以看到,快速排序递归时,先通过partition把数组分隔为两个部分,两个部分“都”要再次递归。

     

    分治法有一个特例,叫减治法。

     

    减治法(Reduce&Conquer),把一个大的问题,转化为若干个子问题(Reduce),这些子问题中“只”解决一个,大的问题便随之解决(Conquer)。这里的关键词是“只”。

     

    二分查找binary_search,BS,是一个典型的运用减治法思想的算法,其伪代码是:

    int BS(int[]arr, int low, inthigh, int target){

             if(low> high) return -1;

             mid= (low+high)/2;

             if(arr[mid]== target) return mid;

             if(arr[mid]> target)

                       return BS(arr, low, mid-1, target);

             else

                       return BS(arr, mid+1, high, target);

    }

     

    从伪代码可以看到,二分查找,一个大的问题,可以用一个mid元素,分成左半区,右半区两个子问题。而左右两个子问题,只需要解决其中一个,递归一次,就能够解决二分查找全局的问题。

     

    通过分治法与减治法的描述,可以发现,分治法的复杂度一般来说是大于减治法的:

    快速排序:O(n*lg(n))

    二分查找:O(lg(n))

     

    话题收回来,快速排序的核心是:

    i = partition(arr, low, high);

     

    这个partition是干嘛的呢?

    顾名思义,partition会把整体分为两个部分。

    更具体的,会用数组arr中的一个元素(默认是第一个元素t=arr[low])为划分依据,将数据arr[low, high]划分成左右两个子数组:


        左半部分,都比t大
        
        
        右半部分,都比t小
        
        
        中间位置i是划分元素
        


    以上述TopK的数组为例,先用第一个元素t=arr[low]为划分依据,扫描一遍数组,把数组分成了两个半区:


        左半区比t大
        
        
        右半区比t小
        
        
        中间是t
        
    partition返回的是t最终的位置i。

     

    很容易知道,partition的时间复杂度是O(n)。

    画外音:把整个数组扫一遍,比t大的放左边,比t小的放右边,最后t放在中间N[i]。

     

    partition和TopK问题有什么关系呢?

    TopK是希望求出arr[1,n]中最大的k个数,那如果找到了第k大的数,做一次partition,不就一次性找到最大的k个数了么?

    画外音:即partition后左半区的k个数。

     

    问题变成了arr[1, n]中找到第k大的数。

     

    再回过头来看看第一次partition,划分之后:

    i = partition(arr, 1, n);


        如果i大于k,则说明arr[i]左边的元素都大于k,于是只递归arr[1, i-1]里第k大的元素即可;
        
        
        如果i小于k,则说明说明第k大的元素在arr[i]的右边,于是只递归arr[i+1, n]里第k-i大的元素即可;
        
    画外音:这一段非常重要,多读几遍。

     

    这就是随机选择算法randomized_select,RS,其伪代码如下:

    int RS(arr, low, high, k){

      if(low== high) return arr[low];

      i= partition(arr, low, high);

      temp= i-low; //数组前半部分元素个数

      if(temp>=k)

          return RS(arr, low, i-1, k); //求前半部分第k大

      else

          return RS(arr, i+1, high, k-i); //求后半部分第k-i大

    }

     

     

    这是一个典型的减治算法,递归内的两个分支,最终只会执行一个,它的时间复杂度是O(n)。

     

    再次强调一下:


        分治法,大问题分解为小问题,小问题都要递归各个分支,例如:快速排序
        
        
        减治法,大问题分解为小问题,小问题只要递归一个分支,例如:二分查找,随机选择
        
     

    通过随机选择(randomized_select),找到arr[1, n]中第k大的数,再进行一次partition,就能得到TopK的结果。

     

    五、总结

    TopK,不难;其思路优化过程,不简单:


        全局排序,O(n*lg(n))
        
        
        局部排序,只排序TopK个数,O(n*k)
        
        
        堆,TopK个数也不排序了,O(n*lg(k))
        
        
        分治法,每个分支“都要”递归,例如:快速排序,O(n*lg(n))


        
        减治法,“只要”递归一个分支,例如:二分查找O(lg(n)),随机选择O(n)
        
        
        TopK的另一个解法:随机选择+partition
        
     

    知其然,知其所以然。

    思路比结论重要。

     

    3.介绍3 包括各种排序的空间及时间复杂度

    二分查找与几种排序方法

     

    更多相关内容
  • [数据结构]堆的经典——TopK问题与堆排序

    千次阅读 多人点赞 2022-03-27 15:43:35
    详细讲解堆中经典的TopK问题与堆排序以及实现源码

    前面这篇文章已经具体讲解过堆的性质与实现了
    数据结构——堆
    在这里插入图片描述

    这篇文章将介绍堆中经典的Topk问题与堆排序

    🍁Topk问题的引入

    要求:从N个数中找出前K个最大的数(N >> K)
    方法一:假设是从100个数中找前10个最大的数,先用快排排降序,前十个就是最大的,时间复杂度O(NlogN)
    方法二:将N个数依次push到大堆中,那么堆顶的元素肯定是最大的,然后popK次,就找到了前K个最大的数,时间复杂度O(N+k*log2N后面会再次证明)。那这应该就是Topk问题了吧,显然不是

    在这里插入图片描述
    当N非常大,为10亿、20亿大到内存中无法存下这些数,只能存储在磁盘中,那上面的两种方式就不适用了

    🌴Topk问题

    虽然无法将N个数都建成大堆,但可以

    • 先将前K个数建为小堆,小堆的特点就是堆顶的数是最小的,大数往堆底沉
    • 当用后N-K个数不断和堆顶比较后然后向下调整后,
    • 最后堆中的K个数就是前K个最大的
    • 时间复杂度为:K+(N-K)* logK 也就是O(NlogK)

    这里建立的是小堆而不是大堆,因为如果是大堆,那么堆顶的数是堆中最大的,和剩下的N-K个数比较时,如果当前堆顶的数就是N个数中最大的,那么就把后面的数都挡在堆外了,这种只能找到N个数中最大的数

    前面已经实现过堆了

    typedef int HPDataType;
    typedef struct Heap
    {
    	HPDataType* p;
    	int size;
    	int capacity;
    }HP;
    
    //堆初始化
    void HeapInit(HP* pc);
    //堆中元素交换
    void HeapSwap(HPDataType* p1, HPDataType* p2);
    //打印元素
    void HeapPrint(HP* pc);
    //堆插入
    void HeapPush(HP* pc, HPDataType x);
    //堆删除
    void HeapPop(HP* pc);
    //堆销毁
    void HeapDestroy(HP* pc);
    //堆判空
    bool HeapEmpty(HP* pc);
    //向上调整
    void AdjustUp(HPDataType* p, int child);
    //向下调整
    AdjustDown(HPDataType* p, int n, int parent);
    //获取堆顶元素
    HPDataType HeapTop(HP* pc);
    

    我们模拟实现从1w个数中找到最大的前10个数

    void PrintTopK(int* p, int N, int K)
    {
    	//前K个数建为小堆
    	HP h1;
    	//初始化
    	HeapInit(&h1);
    	for (int i = 0; i < K; i++)
    	{
    		HeapPush(&h1, p[i]);
    	}
    	//剩余的N-K个数分别与堆顶的元素比较,大于堆顶元素则交换然后向下调整,大的数都沉入堆底
    	for (int i = K; i < N; i++)
    	{
    		if (p[i] > HeapTop(&h1))
    		{
    			HeapPop(&h1);
    			HeapPush(&h1, p[i]);
    		}
    	}
    	HeapPrint(&h1);
    	HeapDestroy(&h1);
    }
    void TopK1()
    {	
    	srand((unsigned int)time(NULL));
    	int N = 10000, K = 10;
    	int* p = (int*)malloc(sizeof(int) * N);
    
    	//将N个数都初始化为小于100万的数
    	for (int i = 0; i < N; i++)
    	{
    		p[i] = rand() % 1000000;
    	}
    	//随机取K个大于100万的数放入数组
    	p[1010] = 1000001;
    	p[2555] = 2000000;
    	p[377] = 3000000;
    	p[4781] = 3003456;
    	p[5433] = 4006754;
    	p[675] = 9874567;
    	p[7954] = 8532876;
    	p[4578] = 3489645;
    	p[6775] = 4892111;
    	p[789] = 9999999;
    	
    	PrintTopK(p, N, K);
    }
    
    int main()
    {
    	TopK1();
    
    	return 0;
    }
    

    在这里插入图片描述再演示一下从文件中读取C语言文件读取
    测试就只选从6个数总找出最大的前3个,这里在text文件中写入了6个数
    在这里插入图片描述测试无误的话就会打印后面的三个数

    
    void TopK2()
    {	
    	int N = 6, K = 3;
    	int* p = (int*)malloc(sizeof(int) * N);
    	FILE* pf = fopen("D:\\桌面\\text.txt", "r");
    	int i = 0;
    	int arr[1] = { 0 };
    	while (fscanf(pf, "%d", arr) != EOF)
    	{
    		p[i] = arr[0];
    		++i;
    	}
    	fclose(pf);
    	pf = NULL;
    
    	PrintTopK(p, N, K);
    }
    
    int main()
    {
    	TopK2();
    
    	return 0;
    }
    

    在这里插入图片描述以上就是Topk问题,关于这些时间复杂度后面会证明,下面先讲堆排序

    🌴堆排序

    如果要对以下数组升序,可以先将数组中的元素建成一个小堆,然后重新pop到数组中,而这样空间复杂度就是O(N)

    int arr[] = { 70, 56, 30, 60, 25, 40 };
    

    堆排序是通过建堆的思想直接在数组中进行排序,空间复杂度为O(1)

    比如我们要建一个小堆,就是不断插入数据,然后向上调整,那么我那就可以利用向上调整的思想,直接在数组中进行排序

    方法一:向上调整法,从左往右遍历数组
    在这里插入图片描述

    #include <stdio.h>
    #include <assert.h>
    
    void HeapSwap(int* p1, int* p2)
    {
    	assert(p1 && p2);
    	int tmp = *p1;
    	*p1 = *p2;
    	*p2 = tmp;
    }
    void AdjustUp(int* p, int child)
    {
    	assert(p);
    	int parent = (child - 1) / 2;
    	while (child > 0)
    	{
    		//小于父亲节点就调整
    		if (p[child] < p[parent])
    		{
    			HeapSwap(&p[child], &p[parent]);
    			child = parent;
    			parent = (child - 1) / 2;
    		}
    		else
    			break;
    	}
    }
    void sortHeap(int* p, int n)
    {
    	assert(p);
    	for (int i = 1; i < n; i++)
    	{
    		AdjustUp(p, i);
    	}
    }
    int main()
    {
    	int arr[] = { 70, 56, 30, 60, 25, 40 };
    	int n = sizeof(arr) / sizeof(arr[0]);
    	sortHeap(arr, n);
    
    	return 0;
    }
    

    方法二:向下调整法,从右往左倒着遍历数组。因为向下调整是由要求的,需要左子树和右子树都是小堆或大堆,所以只能倒着来

    在这里插入图片描述

    #include <stdio.h>
    #include <assert.h>
    
    void HeapSwap(int* p1, int* p2)
    {
    	assert(p1 && p2);
    	int tmp = *p1;
    	*p1 = *p2;
    	*p2 = tmp;
    }
    AdjustDown(int* p, int n, int parent)
    {
    	//左孩子
    	int child = parent * 2 + 1;
    	while (child < n)
    	{
    		//判断是否有右孩子且右孩子小于左孩子
    		if (child + 1 < n && p[child + 1] < p[child])
    			++child;
    		if (p[child] < p[parent])
    		{
    			HeapSwap(&p[child], &p[parent]);
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else
    			break;
    	}
    }
    void sortHeap(int* p, int n)
    {
    	assert(p);
    	int child = n - 1;
    	int end = (child - 1) / 2;
    	while (end >= 0)
    	{
    		AdjustDown(p, n, end);
    		--end;
    	}
    
    }
    int main()
    {
    	int arr[] = { 70, 56, 30, 60, 25, 40 };
    	int n = sizeof(arr) / sizeof(arr[0]);
    	sortHeap(arr, n);
    
    	return 0;
    }
    

    🌴排升序到底选大堆还是小堆

    🌏排升序建小堆分析

    上面我们用向下调整法建成小堆后,堆顶的元素就是最小的,放在数组的第一个位置,那如何选择次小的呢?

    把25不看作堆中的元素,将arr[1]~arr[5]的数据重新建小堆再找次小的数,以此类推,但这样堆的结构就乱了,每次都需要更新堆的根节点,而且建堆的时间复杂度是O(N),那么排成升序的时间复杂度就是N*(N-1)*(N-2)…1也就是O(N2),那么堆排序就没有意义了
    在这里插入图片描述

    🌏排升序建大堆

    参考堆的pop接口,是将堆顶堆尾的数据交换后再--size也就pop掉堆顶的元素了,所以只需要保证交换后堆尾的数最大(这样最大的数就在最后),也就是交换之前堆顶的数最大,这就是大堆的结构了,所以排升序要建大堆
    在这里插入图片描述动图演示:从30开始向下调整
    在这里插入图片描述
    将最大的数跟最后一个数交换,然后不把最后一个数看作堆中的元素,堆顶的数向下调整后就可以选出次小的数,以此类推最后就能排出升序,向下调整的时间复杂度为O(log2N)
    在这里插入图片描述

    int arr[] = { 70, 56, 30, 60, 25, 40 };
    

    在这里插入图片描述

    #include <stdio.h>
    #include <assert.h>
    
    void HeapSwap(int* p1, int* p2)
    {
    	assert(p1 && p2);
    	int tmp = *p1;
    	*p1 = *p2;
    	*p2 = tmp;
    }
    AdjustDown(int* p, int n, int parent)
    {
    	//左孩子
    	int child = parent * 2 + 1;
    	while (child < n)
    	{
    		//判断是否有右孩子且右孩子大于左孩子
    		if (child + 1 < n && p[child + 1] > p[child])
    			++child;
    		if (p[child] > p[parent])
    		{
    			HeapSwap(&p[child], &p[parent]);
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else
    			break;
    	}
    }
    //这里实现堆排序一个向下调整就解决了,所以没有用向上调整
    void sortHeap(int* p, int n)
    {
    	assert(p);
    	int child = n - 1;
    	//从最后一个非叶子节点开始,向下调整
    	int first = (child - 1) / 2;
    	while (first >= 0)
    	{	
    		AdjustDown(p, n, first);
    		--first;
    	}
    	int right = n - 1;
    	while (right > 0)
    	{
    		HeapSwap(p, p + right);
    		AdjustDown(p, right, 0);
    		--right;
    	}
    
    }
    int main()
    {
    	int arr[] = { 70, 56, 30, 60, 25, 40 };
    	int n = sizeof(arr) / sizeof(arr[0]);
    	sortHeap(arr, n);
    	for (int i = 0; i < n; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	
    	return 0;
    }
    

    所以堆排序本质上是一种选择排序

    • 排升序,建大堆
    • 排降序,建小堆

    大小堆直接的转化也是非常容易的,只需要调整向上和向下调整的比较关系
    在这里插入图片描述

    🍁时间复杂度证明

    🌏调整算法的时间复杂度

    为了方便, 以堆为满二叉树证明
    满二叉树的节点个数n=2h-1–>h=log2n+1
    向上调整或向下调整的时间复杂度与树的高的有关,所以插入一个数据的时间复杂度为O(log2N),插入N个数据(建堆)的时间复杂度是O(N*log2N),这是用向上调整建堆的时间复杂度,用向下调整建堆的时间复杂度实际是O(N),因为向上调整需要从第2层~第h层,而向下调整是从第h-1层~第一层,所以向下调整最后一层不需要调,向上调整第1层不需要调,而最后一层节点的个数是2h-1,几乎占了总节点个数2h-1的一半了
    在这里插入图片描述

    🌏建堆的时间复杂度

    建堆的时间复杂度与向上调整或向下调整有关,考虑最坏情况:
    在这里插入图片描述

    总结:
    TopK问题:通过建小堆,找到N个数中最大的前K个,建大堆,找到N个数中最小的前K个
    堆排序:排升序建大堆,排降序建小堆

    以上就是堆中经典的Topk问题与堆排序了,希望我的文章对你有所帮助,欢迎👍点赞 ,📝评论,🌟关注,⭐️收藏
    在这里插入图片描述

    展开全文
  • Top K算法

    2021-02-12 20:09:01
    Top K算法问题描述:从arr[1, n]这n个数中,找出最大的k个数,这就是经典的TopK问题。栗子:从arr[1, 12]={5,3,7,1,8,2,9,4,7,2,6,6} 这n=12个数中,找出最大的k=5个。一、排序 排序是最容易想到的方法,将n个数排序...

    Top K算法

    问题描述:

    从arr[1, n]这n个数中,找出最大的k个数,这就是经典的TopK问题。

    栗子:

    从arr[1, 12]={5,3,7,1,8,2,9,4,7,2,6,6} 这n=12个数中,找出最大的k=5个。

    一、排序

    b80462352a8155bc683e9d2a00a715c1.png

    排序是最容易想到的方法,将n个数排序之后,取出最大的k个,即为所得。

    伪代码:

    sort(arr, 1, n);

    return arr[1, k];

    时间复杂度:O(n*lg(n))

    分析:明明只需要TopK,却将全局都排序了,这也是这个方法复杂度非常高的原因。那能不能不全局排序,而只局部排序呢?这就引出了第二个优化方法。

    二、局部排序

    不再全局排序,只对最大的k个排序。

    57482d417cde3d40563bc45e3ffa001c.png

    冒泡是一个很常见的排序方法,每冒一个泡,找出最大值,冒k个泡,就得到TopK。

    伪代码:

    for(i=1 to k){

    ​ bubble_find_max(arr,i);

    }

    return arr[1, k];

    时间复杂度:O(n*k)

    分析:冒泡,将全局排序优化为了局部排序,非TopK的元素是不需要排序的,节省了计算资源。不少朋友会想到,需求是TopK,是不是这最大的k个元素也不需要排序呢?这就引出了第三个优化方法。

    三、堆

    思路:只找到TopK,不排序TopK。

    4c1de2a8e96a7cb4d7d549fe226ec1cf.png

    先用前k个元素生成一个小顶堆,这个小顶堆用于存储,当前最大的k个元素。

    1625198391e699a668b410b9aac4fb88.png

    接着,从第k+1个元素开始扫描,和堆顶(堆中最小的元素)比较,如果被扫描的元素大于堆顶,则替换堆顶的元素,并调整堆,以保证堆内的k个元素,总是当前最大的k个元素。

    09886a6afbeedc0c890b4103f4925e93.png

    直到,扫描完所有n-k个元素,最终堆中的k个元素,就是猥琐求的TopK。

    伪代码:

    heap[k] = make_heap(arr[1, k]);

    for(i=k+1 to n){

    ​ adjust_heap(heep[k],arr[i]);

    }

    return heap[k];

    时间复杂度:O(n*lg(k))

    画外音:n个元素扫一遍,假设运气很差,每次都入堆调整,调整时间复杂度为堆的高度,即lg(k),故整体时间复杂度是n*lg(k)。

    分析:堆,将冒泡的TopK排序优化为了TopK不排序,节省了计算资源。堆,是求TopK的经典算法,那还有没有更快的方案呢?

    四、随机选择

    随机选择算在是《算法导论》中一个经典的算法,其时间复杂度为O(n),是一个线性复杂度的方法。

    这个方法并不是所有同学都知道,为了将算法讲透,先聊一些前序知识,一个所有程序员都应该烂熟于胸的经典算法:快速排序。

    其伪代码是:

    void quick_sort(int[]arr, int low, inthigh){

    ​ if(low== high) return;

    ​ int i = partition(arr, low, high);

    ​ quick_sort(arr, low, i-1);

    ​ quick_sort(arr, i+1, high);

    }

    其核心算法思想是,分治法。

    分治法(Divide&Conquer),把一个大的问题,转化为若干个子问题(Divide),每个子问题“都”解决,大的问题便随之解决(Conquer)。这里的关键词是**“都”**。从伪代码里可以看到,快速排序递归时,先通过partition把数组分隔为两个部分,两个部分“都”要再次递归。

    分治法有一个特例,叫减治法。

    减治法(Reduce&Conquer),把一个大的问题,转化为若干个子问题(Reduce),这些子问题中“只”解决一个,大的问题便随之解决(Conquer)。这里的关键词是**“只”**。

    二分查找binary_search,BS,是一个典型的运用减治法思想的算法,其伪代码是:

    int BS(int[]arr, int low, inthigh, int target){

    ​ if(low> high) return -1;

    ​ mid= (low+high)/2;

    ​ if(arr[mid]== target) return mid;

    ​ if(arr[mid]> target)

    ​ return BS(arr, low, mid-1, target);

    ​ else

    ​ return BS(arr, mid+1, high, target);

    }

    从伪代码可以看到,二分查找,一个大的问题,可以用一个mid元素,分成左半区,右半区两个子问题。而左右两个子问题,只需要解决其中一个,递归一次,就能够解决二分查找全局的问题。

    通过分治法与减治法的描述,可以发现,分治法的复杂度一般来说是大于减治法的:

    快速排序:O(n*lg(n))

    二分查找:O(lg(n))

    话题收回来,快速排序的核心是:

    i = partition(arr, low, high);

    这个partition是干嘛的呢?

    顾名思义,partition会把整体分为两个部分。

    更具体的,会用数组arr中的一个元素(默认是第一个元素t=arr[low])为划分依据,将数据arr[low, high]划分成左右两个子数组:

    左半部分,都比t大

    右半部分,都比t小

    中间位置i是划分元素

    66ed0557aa547543ab165cdfd09988e1.png

    以上述TopK的数组为例,先用第一个元素t=arr[low]为划分依据,扫描一遍数组,把数组分成了两个半区:

    左半区比t大

    右半区比t小

    中间是t

    partition返回的是t最终的位置i。

    很容易知道,partition的时间复杂度是O(n)。

    partition和TopK问题有什么关系呢?

    TopK是希望求出arr[1,n]中最大的k个数,那如果找到了第k大的数,做一次partition,不就一次性找到最大的k个数了么?

    问题变成了arr[1, n]中找到第k大的数。

    再回过头来看看第一次partition,划分之后:

    i = partition(arr, 1, n);

    如果i大于k,则说明arr[i]左边的元素都大于k,于是只递归arr[1, i-1]里第k大的元素即可;

    如果i小于k,则说明说明第k大的元素在arr[i]的右边,于是只递归arr[i+1, n]里第k-i大的元素即可;

    这就是随机选择算法randomized_select,RS,其伪代码如下:

    int RS(arr, low, high, k){

    if(low== high) return arr[low];

    i= partition(arr, low, high);

    temp= i-low; //数组前半部分元素个数

    if(temp>=k)

    return RS(arr, low, i-1, k); //求前半部分第k大

    else

    return RS(arr, i+1, high, k-i); //求后半部分第k-i大

    }

    5b17d4735ec01ba028c593e49b3859f2.png

    这是一个典型的减治算法,递归内的两个分支,最终只会执行一个,它的时间复杂度是O(n)。

    再次强调一下:

    分治法,大问题分解为小问题,小问题都要递归各个分支,例如:快速排序

    减治法,大问题分解为小问题,小问题只要递归一个分支,例如:二分查找,随机选择

    通过随机选择(randomized_select),找到arr[1, n]中第k大的数,再进行一次partition,就能得到TopK的结果。

    五、总结

    TopK,不难;其思路优化过程,不简单:

    全局排序,O(n*lg(n))

    局部排序,只排序TopK个数,O(n*k)

    堆,TopK个数也不排序了,O(n*lg(k))

    分治法,每个分支“都要”递归,例如:快速排序,O(n*lg(n))

    减治法,“只要”递归一个分支,例如:二分查找O(lg(n)),随机选择O(n)

    TopK的另一个解法:随机选择+partition

    仅做笔记用,如有侵权,联系作者删除

    展开全文
  • TopK算法 排序

    万次阅读 2018-02-23 09:41:09
    amp;fps=1 1、查找最大的k个元素 ...我们知道,快速排序平均所费时间为n*logn,从小到大排序这n个数,然后再遍历序列中后k个元素输出,即可,总的时间复杂度为O(n*logn+k)=O(n*logn)。...

    本文转自:http://blog.csdn.net/Together_CZ/article/details/65945838?locationNum=15&fps=1

    1、查找最大的k个元素

    1、排序,快速排序。我们知道,快速排序平均所费时间为n*logn,从小到大排序这n个数,然后再遍历序列中后k个元素输出,即可,总的时间复杂度为O(n*logn+k)=O(n*logn)。

    2、排序,选择排序。用选择或交换排序,即遍历n个数,先把最先遍历到得k个数存入大小为k的数组之中,对这k个数,利用选择或交换排序,找到k个数中的最小数kmin(kmin设为k个元素的数组中最小元素),用时O(k)(你应该知道,插入或选择排序查找操作需要O(k)的时间),后再继续遍历后n-k个数,x与kmin比较:如果x > kmin,则x代替kmin,并再次重新找出k个元素的数组中最小元素kmin‘(多谢jiyeyuran 提醒修正);如果x < kmin,则不更新数组。也就是,每次把k个元素的数组中最小的元素替换掉。这样,每次更新或不更新数组的所用的时间为O(k)或O(0),整趟下来,总的时间复杂度平均下来为:n*O(k)=O(n*k)。

    3、维护k个元素的最小堆,原理与上述第2个方案一致,即用容量为k的最小堆存储最先遍历到的k个数,并假设它们即是最大的k个数,建堆费时O(k),并调整堆(费时O(logk))后,有k1>k2>…kmin(kmin设为小顶堆中最小元素)。继续遍历数列,每次遍历一个元素x,与堆顶元素比较,若x>kmin,则更新堆(用时logk),否则不更新堆。这样下来,总费时O(k*logk+(n-k)*logk)=O(n*logk)。此方法得益于在堆中,查找等各项操作时间复杂度均为logk(不然,就如上述思路2所述:直接用数组也可以找出最大的k个元素,用时O(n*k))。

    4、按编程之美第141页上解法二的所述,类似快速排序的划分方法,N个数存储在数组S中,再从数组中随机选取一个数X,把数组划分为Sa和Sb俩部分,Sa>=X>=Sb,如果要查找的k个元素小于Sa的元素个数,则返回Sa中较大的k个元素,否则返回Sa中所有的元素+Sb中最大的k-|Sa|个元素。不断递归下去,把问题分解成更小的问题,平均时间复杂度为O(N)。

    2、什么是哈希表?

    哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

    哈希表hashtable(key,value) 的做法其实很简单,就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。

    而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。

    3、应用实例

    1、搜索引擎热门查询统计:Hash表+堆!!! 
    搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。 
    假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。),请你统计最热门的10个查询串,要求使用的内存不能超过1G。

    问题解析:

    要统计最热门查询,首先就是要统计每个Query出现的次数,然后根据统计结果,找出Top 10。所以我们可以基于这个思路分两步来设计该算法。

    第一步:Query统计

    Query统计有以下俩个方法,可供选择:

    1、排序法

    题目中有明确要求,那就是内存不能超过1G。一千万条记录,每条记录是255Byte,很显然要占据2.375G内存,这个条件就不满足要求了。

    让我们回忆一下数据结构课程上的内容,当数据量比较大而且内存无法装下的时候,我们可以采用外排序的方法来进行排序,这里我们可以采用归并排序,因为归并排序有一个比较好的时间复杂度O(NlgN)。

    排完序之后我们再对已经有序的Query文件进行遍历,统计每个Query出现的次数,再次写入文件中。

    综合分析一下,排序的时间复杂度是O(NlgN),而遍历的时间复杂度是O(N),因此该算法的总体时间复杂度就是O(N+NlgN)=O(NlgN)。

    2、Hash Table法

    能不能有更好的方法时间复杂度更低呢?

    题目中说明了,虽然有一千万个Query,但是由于重复度比较高,因此事实上只有300万的Query,每个Query255Byte,因此我们可以考虑把他们都放进内存中去,Hash Table绝对是我们优先的选择,因为Hash Table的查询速度非常的快,几乎是O(1)的时间复杂度。

    那么,我们的算法就有了:维护一个Key为Query字串,Value为该Query出现次数的HashTable,每次读取一个Query,如果该字串不在Table中,那么加入该字串,并且将Value值设为1;如果该字串在Table中,那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内完成了对该海量数据的处理。

    相比算法1:在时间复杂度上提高了一个数量级,为O(N),但不仅仅是时间复杂度上的优化,该方法只需要IO数据文件一次,而算法1的IO次数较多的。

    第二步:找出Top 10

    算法一:普通排序

    排序算法的时间复杂度是NlgN,在本题目中,三百万条记录,用1G内存是可以存下的。

    算法二:部分排序

    题目要求是求出Top 10,因此我们没有必要对所有的Query都进行排序,我们只需要维护一个10个大小的数组,初始化放入10个Query,按照每个Query的统计次数由大到小排序,然后遍历这300万条记录,每读一条记录就和数组最后一个Query对比,如果小于这个Query,那么继续遍历,否则,将数组中最后一条数据淘汰,加入当前的Query。最后当所有的数据都遍历完毕之后,那么这个数组中的10个Query便是我们要找的Top10了。

    不难分析出,这样,算法的最坏时间复杂度是N*K, 其中K是指top多少。

    算法三:堆

    在算法二中,我们已经将时间复杂度由NlogN优化到NK,不得不说这是一个比较大的改进了,可是有没有更好的办法呢?

    每次查找的时候可以采用二分的方法查找,这样操作的复杂度就降到了logK。能快速查找,又能快速移动元素的数据结构:那就是堆。

    借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此到这里,我们的算法可以改进为这样,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比。!!!

    具体过程是,堆顶存放的是整个堆中最小的数,现在遍历N个数,把最先遍历到的k个数存放到最小堆中,并假设它们就是我们要找的最大的k个数,X1>X2…Xmin(堆顶),而后遍历后续的N-K个数,一一与堆顶元素进行比较,如果遍历到的Xi大于堆顶元素Xmin,则把Xi放入堆中,而后更新整个堆,更新的时间复杂度为logK,如果Xi < Xmin,则不更新堆,整个过程的复杂度为O(K)+O((N-K)*logK)=O(N*logK)。

    总结:

    至此,算法就完全结束了,经过上述第一步、先用Hash表统计每个Query出现的次数,O(N);然后第二步、采用堆数据结构找出Top 10,N*O(logK)。所以,我们最终的时间复杂度是:O(N) + N’*O(logK)。!!!!!!!!(N为1000万,N’为300万)。

    http://blog.csdn.net/v_JULY_v/article/details/6256463#comments

     

    摊还分析—算法导论第十七章


    摊还分析是用来评价程序中的一个操作序列的平均代价,有时可能某个操作的代价特别高,但总体上来看也并非那么糟糕,可以形象的理解为把高代价的操作“分摊”到其他操作上去了,要求的就是均匀分摊后的平均代价。

    摊还分析有三种常用的技术:聚合分析,核算法,势能法。

    首先看个例子,现在有三种操作,push(s),pop(s),mutlipop(s,k),push(s),统称为栈操作。 push(s)每次只能压一个数据,所以规定操作的代价为1,pop(s)每次只能弹一个数据,所以也规定操作的代价为1,而mutlipop(s,k),内部实现的是一个循环弹出,每执行一次的代价为k(k < n,n为栈的最大容量)。那么现在问题来了,我想分析下执行n次栈操作最坏情况下的时间复杂度是多少?第一反应应该就是这样想的,mutlipop(s,k)的代价最高,最高位k=n;

    执行n次的最坏情况当然就是o(n2)啦,但实际上并非如此。

    聚合分析要求我们要总体看问题,首先mutlipop(s,k)也是个弹栈的操作,当栈里有数据的时候才执行有效,所以上述提到的o(n2)是不科学的,而push(s),pop(s)的代价是1,可想而知最坏的情况当然是前n-1次操作都是压栈,而最后一次才执行mutlipop(s,n-1),这样的代价也只有2n-2,时间复杂度为o(n),平均下来每个操作的摊还代价就为o(1)了。

    核算法比较好理解,进行摊还分析时,摊还的代价有可能多于实际的代价,也有可能少于实际的代价,多于实际代价的差额会存进一个数据结构中,称为信用,而当遇到少于实际代价的时候就可以用这些信用来填充了。注意这些什么算法提供的只是思路,求出一系列操作代价的上界的思路,具体的做法还是要自己思考的。

    同样是压栈的例子,我们可以赋给Push(s)操作的摊还代价是2,相当于自己使用了1,而压进去的必定会弹出,剩下的1就作为弹出时的费用,这样pop(s)和mutlipop(s,k)的摊还代价就为0,这样做有什么意义?试着现在思考下题目中的问题(斜体部分),那么可想最糟糕的情况无非就是所有操作都是Push(s),代价为2n,并不像聚合代价那样需要考虑其他两个操作(摊还代价为0),时间复杂度为O(n)。

    势能法 
    势能法其实核算法有点相似,也有预付差额的,但不叫信用,而叫势能,势能法是从整体上看的,不像核算法那样具体到某个操作,而是整体的势能。

    势能法定义了一条公式;

                     Ci(摊还)=Ci(实际)+f(Di)-f(Di-1)          (1)
    

    累加可得总摊还代价的公式为;

                     Ci(总摊还)= Ci(总实际)+ f(Di)-f(D0)        (2)
    

    其中Ci 为每步操作的代价,f(Di)表示执行了第i个操作后的势能,那个这个公式就可以理解为 第i步操作的摊还代价等于第i步操作的实际代价加上从第i-1步操作到第i步操作的势能变化,理解这个后,再来看栈操作的例子。

    同样Push(s)、pop(s)的代价为1, mutlipop(s,k)的代价为k,我们规定入栈一个元素势能加1,弹出一个元素势能减1,那么f(Di)永远为非负,而f(D0)等于0,再根据上面的公式(2)即可知道这个又这里就可以确定总摊还代价是总实际代价的上界,所以现在要求的就是总摊还代价。

    根据公式(1)可以得到Push(s)的摊还代价为2,pop(s)的摊还代价为0,mutlipop(s,k)的摊还代价也为0 (因为弹栈势能要减,刚好和代价抵消,也可以看做势能都用来支付代价了,所以下降了),那么又回到了核算法了,可得时间复杂度为O(n)。

    以上转自http://blog.csdn.net/mypongo/article/details/42189001

    练习17.1-3 
    假定我们对一个数据结构执行一个由n个操作组成的操作序列,当i严格为2的幂时,第i个操作的代价为i,否则代价为1。使用聚合分析确定每个操作的摊还代价。 
    这里写图片描述

    练习17.2-2 
    用核算法重做练习17.1-3 
    这里写图片描述 
    这里写图片描述


    转自http://blog.csdn.net/xiazdong/article/details/8462393

    stable sort:插入排序、冒泡排序、归并排序、计数排序、基数排序、桶排序。 
    unstable sort:选择排序、快速排序、堆排序。

    插入排序,冒泡排序和快速排序的排序趟数与序列的初始状态有关!!! 
    堆排序和选择排序的排序次数与初始状态无关,即最好情况和最坏情况都一样!!!

    一、插入排序

    特点:stable sort、In-place sort 
    最优复杂度:当输入数组就是排好序的时候,复杂度为O(n),而快速排序在这种情况下会产生O(n^2)的复杂度。 
    最差复杂度:当输入数组为倒序时,复杂度为O(n^2) 
    插入排序比较适合用于“少量元素的数组”。

    其实插入排序的复杂度和逆序对的个数一样,当数组倒序时,逆序对的个数为n(n-1)/2,因此插入排序复杂度为O(n^2)。 
    算法导论2-4中有关于逆序对的介绍。

    伪代码:

    这里写图片描述

    证明算法正确性:

    循环不变式:在每次循环开始前,A[1…i-1]包含了原来的A[1…i-1]的元素,并且已排序。

    初始:i=2,A[1…1]已排序,成立。 
    保持:在迭代开始前,A[1…i-1]已排序,而循环体的目的是将A[i]插入A[1…i-1]中,使得A[1…i]排序,因此在下一轮迭代开 始前,i++,因此现在A[1…i-1]排好序了,因此保持循环不变式。 
    终止:最后i=n+1,并且A[1…n]已排序,而A[1…n]就是整个数组,因此证毕。

    而在算法导论2.3-6中还问是否能将伪代码第6-8行用二分法实现?

    实际上是不能的。因为第6-8行并不是单纯的线性查找,而是还要移出一个空位让A[i]插入,因此就算二分查找用O(lgn)查到了插入的位置,但是还是要用O(n)的时间移出一个空位。

    问:快速排序(不使用随机化)是否一定比插入排序快?

    答:不一定,当输入数组已经排好序时,插入排序需要O(n)时间,而快速排序需要O(n^2)时间。

    递归版插入排序 
    这里写图片描述

    二、冒泡排序

    特点:stable sort、In-place sort 
    思想:通过两两交换,像水中的泡泡一样,小的先冒出来,大的后冒出来。 
    最坏运行时间:O(n^2) 
    最佳运行时间:O(n^2)(当然,也可以进行改进使得最佳运行时间为O(n))

    算法导论思考题2-2中介绍了冒泡排序。

    伪代码: 
    这里写图片描述 
    证明算法正确性:

    运用两次循环不变式,先证明第4-6行的内循环,再证明外循环。

    内循环不变式:在每次循环开始前,A[j]是A[j…n]中最小的元素。

    初始:j=n,因此A[n]是A[n…n]的最小元素。 
    保持:当循环开始时,已知A[j]是A[j…n]的最小元素,将A[j]与A[j-1]比较,并将较小者放在j-1位置,因此能够说明A[j-1]是A[j-1…n]的最小元素,因此循环不变式保持。 
    终止:j=i,已知A[i]是A[i…n]中最小的元素,证毕。

    接下来证明外循环不变式:在每次循环之前,A[1…i-1]包含了A中最小的i-1个元素,且已排序:A[1]<=A[2]<=…<=A[i-1]。

    初始:i=1,因此A[1..0]=空,因此成立。 
    保持:当循环开始时,已知A[1…i-1]是A中最小的i-1个元素,且A[1]<=A[2]<=…<=A[i-1],根据内循环不变式,终止时A[i]是A[i…n]中最小的元素,因此A[1…i]包含了A中最小的i个元素,且A[1]<=A[2]<=…<=A[i-1]<=A[i] 
    终止:i=n+1,已知A[1…n]是A中最小的n个元素,且A[1]<=A[2]<=…<=A[n],得证。

    在算法导论思考题2-2中又问了”冒泡排序和插入排序哪个更快“呢?

    一般的人回答:“差不多吧,因为渐近时间都是O(n^2)”。 
    但是事实上不是这样的,插入排序的速度直接是逆序对的个数,而冒泡排序中执行“交换“的次数是逆序对的个数,因此冒泡排序执行的时间至少是逆序对的个数,因此插入排序的执行时间至少比冒泡排序快。

    递归版冒泡排序 
    这里写图片描述

    改进版冒泡排序

    最佳运行时间:O(n) 
    最坏运行时间:O(n^2) 
    这里写图片描述

    三、选择排序

    特性:In-place sort,unstable sort。 
    思想:每次找一个最小值。 
    最好情况时间:O(n^2)。 
    最坏情况时间:O(n^2)。

    定义:首先,选出数组中最小的元素,将它与数组中第一个元素交换。然后找出次小的元素,并将它与数组中第二个元素交换。按照这种方法一直进行下去,直到整个数组排完序。

    交换次数:N-1

    伪代码: 
    这里写图片描述 
    证明算法正确性:

    循环不变式: A[1…i-1]包含了A中最小的i-1个元素,且已排序。

    初始: i=1,A[1…0]=空,因此成立。 
    保持:在某次迭代开始之前,保持循环不变式,即A[1…i-1]包含了A中最小的i-1个元素,且已排序,则进入循环体后,程序从A[i…n]中找出最小值放在A[i]处,因此A[1…i]包含了A中最小的i个元素,且已排序,而i++,因此下一次循环之前,保持循环不变式:A[1..i-1]包含了A中最小的i-1个元素,且已排序。 
    终止: i=n,已知A[1…n-1]包含了A中最小的i-1个元素,且已排序,因此A[n]中的元素是最大的,因此A[1…n]已排序,证毕。

    算法导论2.2-2中问了”为什么伪代码中第3行只有循环n-1次而不是n次”?

    在循环不变式证明中也提到了,如果A[1…n-1]已排序,且包含了A中最小的n-1个元素,则A[n]肯定是最大的,因此肯定是已排序的。

    递归版选择排序 
    这里写图片描述

    四、归并排序

    特点:stable sort、Out-place sort 
    思想:运用分治法思想解决排序问题。 
    最坏情况运行时间:O(nlgn) 
    最佳运行时间:O(nlgn)

    分治法介绍:分治法就是将原问题分解为多个独立的子问题,且这些子问题的形式和原问题相似,只是规模上减少了,求解完子问题后合并结果构成原问题的解。 
    分治法通常有3步:Divide(分解子问题的步骤) 、 Conquer(递归解决子问题的步骤)、 Combine(子问题解求出来后合并成原问题解的步骤)。 
    假设Divide需要f(n)时间,Conquer分解为b个子问题,且子问题大小为a,Combine需要g(n)时间,则递归式为: 
    T(n)=bT(n/a)+f(n)+g(n)

    算法导论思考题4-3(参数传递)能够很好的考察对于分治法的理解。

    就如归并排序,Divide的步骤为m=(p+q)/2,因此为O(1),Combine步骤为merge()函数,Conquer步骤为分解为2个子问题,子问题大小为n/2,因此: 
    归并排序的递归式:T(n)=2T(n/2)+O(n)

    而求解递归式的三种方法有: 
    (1)替换法:主要用于验证递归式的复杂度。 
    (2)递归树:能够大致估算递归式的复杂度,估算完后可以用替换法验证。 
    (3)主定理:用于解一些常见的递归式。

    伪代码: 
    这里写图片描述

    证明算法正确性:

    其实我们只要证明merge()函数的正确性即可。 
    merge函数的主要步骤在第25~31行,可以看出是由一个循环构成。

    循环不变式:每次循环之前,A[p…k-1]已排序,且L[i]和R[j]是L和R中剩下的元素中最小的两个元素。 
    初始:k=p,A[p…p-1]为空,因此已排序,成立。 
    保持:在第k次迭代之前,A[p…k-1]已经排序,而因为L[i]和R[j]是L和R中剩下的元素中最小的两个元素,因此只需要将L[i]和R[j]中最小的元素放到A[k]即可,在第k+1次迭代之前A[p…k]已排序,且L[i]和R[j]为剩下的最小的两个元素。 
    终止:k=q+1,且A[p…q]已排序,这就是我们想要的,因此证毕。

    归并排序的例子: 
    这里写图片描述 
    问:归并排序的缺点是什么?

    答:他是Out-place sort,因此相比快排,需要很多额外的空间。

    问:为什么归并排序比快速排序慢?

    答:虽然渐近复杂度一样,但是归并排序的系数比快排大。

    问:对于归并排序有什么改进?

    答:就是在数组长度为k时,用插入排序,因为插入排序适合对小数组排序。在算法导论思考题2-1中介绍了。复杂度为O(nk+nlg(n/k)) ,当k=O(lgn)时,复杂度为O(nlgn)

    五、快速排序

    基本思想:在待排序的N个记录中任意取一个记录,把该记录放在最终位置后,数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分,所有比它大的放置在后一部分,并把该记录排在这两部分的中间,这个过程称作一次快速排序。重复上述过程,直到每一部分内只有一个记录为止。 
    特性:unstable sort、In-place sort。 
    最坏运行时间:当输入数组已排序时,时间为O(n^2),当然可以通过随机化来改进(shuffle array 或者 randomized select pivot),使得期望运行时间为O(nlgn)。 
    最佳运行时间:O(nlgn) 
    快速排序的思想也是分治法。 
    当输入数组的所有元素都一样时,不管是快速排序还是随机化快速排序的复杂度都为O(n^2),而在算法导论第三版的思考题7-2中通过改变Partition函数,从而改进复杂度为O(n)。

    注意:只要partition的划分比例是常数的,则快排的效率就是O(nlgn),比如当partition的划分比例为10000:1时(足够不平衡了),快排的效率还是O(nlgn)

    “A killer adversary for quicksort”这篇文章很有趣的介绍了怎么样设计一个输入数组,使得quicksort运行时间为O(n^2)。

    伪代码: 
    这里写图片描述

    随机化partition的实现: 
    这里写图片描述

    改进当所有元素相同时的效率的Partition实现: 
    这里写图片描述

    证明算法正确性:

    对partition函数证明循环不变式:A[p…i]的所有元素小于等于pivot,A[i+1…j-1]的所有元素大于pivot。 
    初始:i=p-1,j=p,因此A[p…p-1]=空,A[p…p-1]=空,因此成立。 
    保持:当循环开始前,已知A[p…i]的所有元素小于等于pivot,A[i+1…j-1]的所有元素大于pivot,在循环体中, 
    -如果A[j]>pivot,那么不动,j++,此时A[p…i]的所有元素小于等于pivot,A[i+1…j-1]的所有元素大于pivot。 
    -如果A[j]<=pivot,则i++,A[i+1]>pivot,将A[i+1]和A[j]交换后,A[P…i]保持所有元素小于等于pivot,而A[i+1…j-1]的所有元素大于pivot。 
    终止:j=r,因此A[p…i]的所有元素小于等于pivot,A[i+1…r-1]的所有元素大于pivot。

    六、堆排序

    1964年Williams提出。

    特性:unstable sort、In-place sort。 
    最优时间:O(nlgn) 
    最差时间:O(nlgn) 
    此篇文章介绍了堆排序的最优时间和最差时间的证明:http://blog.csdn.net/xiazdong/article/details/8193625 
    思想:运用了最小堆、最大堆这个数据结构,而堆还能用于构建优先队列。

    优先队列应用于进程间调度、任务调度等。 
    堆数据结构应用于Dijkstra、Prim算法。 
    这里写图片描述

    证明算法正确性:

    (1)证明build_max_heap的正确性: 
    循环不变式:每次循环开始前,A[i+1]、A[i+2]、…、A[n]分别为最大堆的根。

    初始:i=floor(n/2),则A[i+1]、…、A[n]都是叶子,因此成立。 
    保持:每次迭代开始前,已知A[i+1]、A[i+2]、…、A[n]分别为最大堆的根,在循环体中,因为A[i]的孩子的子树都是最大堆,因此执行完MAX_HEAPIFY(A,i)后,A[i]也是最大堆的根,因此保持循环不变式。 
    终止:i=0,已知A[1]、…、A[n]都是最大堆的根,得到了A[1]是最大堆的根,因此证毕。

    (2)证明heapsort的正确性: 
    循环不变式:每次迭代前,A[i+1]、…、A[n]包含了A中最大的n-i个元素,且A[i+1]<=A[i+2]<=…<=A[n],且A[1]是堆中最大的。

    初始:i=n,A[n+1]…A[n]为空,成立。 
    保持:每次迭代开始前,A[i+1]、…、A[n]包含了A中最大的n-i个元素,且A[i+1]<=A[i+2]<=…<=A[n],循环体内将A[1]与A[i]交换,因为A[1]是堆中最大的,因此A[i]、…、A[n]包含了A中最大的n-i+1个元素且A[i]<=A[i+1]<=A[i+2]<=…<=A[n],因此保持循环不变式。 
    终止:i=1,已知A[2]、…、A[n]包含了A中最大的n-1个元素,且A[2]<=A[3]<=…<=A[n],因此A[1]<=A[2]<=A[3]<=…<=A[n],证毕。

    七、计数排序

    特性:stable sort、out-place sort。 
    最坏情况运行时间:O(n+k) 
    最好情况运行时间:O(n+k)

    当k=O(n)时,计数排序时间为O(n)

    伪代码: 
    B[n]存放排序结果;C[k+1]提供临时存储区 
    这里写图片描述 
    算法的步骤如下:

    1、找出待排序的数组中最大和最小的元素 
    2、统计数组中每个值为t的元素出现的次数,存入数组C的第t项 
    3、对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加) 
    4、反向填充目标数组:将每个元素t放在新数组的第C(t)项,每放一个元素就将C(t)减去1 
    例子:

    假设数字范围在 09. 
    输入数据: 1, 4, 1, 2, 7, 5, 2
      1) 使用一个数组记录每个数组出现的次数
      Index:     0  1  2  3  4  5  6  7  8  9
      Count:     0  2  2  0   1  1  0  1  0  0
    
      2) 累加所有计数(从C中的第一个元素开始,每一项和前一项相加)
      Index:     0  1  2  3  4  5  6  7  8  9
      Count:     0  2  4  4  5  6  6  7  7  7
    
    更改过的计数数组就表示 每个元素在输出数组中的位置
    
      3) 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1
     例如对于: 1, 4, 1, 2, 7, 5, 2. 1 的位置是 2.1放在输出数组的第2个位置.并把计数减 1,下一个1出现的时候就放在了第1个位置。(方
    向可以保持稳定)
       
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    习题8.2-4 
    给出一个算法,使之对于给定介于0和k之间的n个整数进行预处理,并能在O(1)时间内,回答出输入的整数中有多少个落在区间[a..b]内。你给出的算法的预处理时间应为Θ(n + k)。

    用一个数组C,记录小于或等于其每个下标的值的元素个数。C[b] - C[a-1]为落在区间内的元素个数。

    #include <stdio.h>
    #include <stdlib.h>
    
    int count(int A[], int length, int k, int a, int b);
    
    int main(){
        int num, i, k, a, b, cnt;
        printf("Input the k:\n");
        scanf("%d", &k);
        printf("Input the a and b:\n");
        scanf("%d %d", &a, &b);
        printf("Input the number of the elements:\n");
        scanf("%d", &num);
        int *array = malloc((num + 1) * sizeof(int));
        printf("Input the element:");
        for(i = 1; i <= num; i++){
            scanf("%d", &array[i]);
        }
    
        cnt = count(array, num, k, a, b);
        printf("The number of the elements which are in the [a..b] is %d\n", cnt);
        return 0;
    }
    
    int count(int A[], int length, int k, int a, int b){
        int *C = malloc((k + 1) * sizeof(int));
        for(int i = 0; i <= k; i++)
            C[i] = 0;
        for(int j = 1; j <= length; j++)
            C[A[j]]++;
    
        for(int i = 1; i <= k; i++)
            C[i] += C[i-1];
    
        return C[b] - C[a-1] ;
    }
       
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    八、基数排序

    本文假定每位的排序是计数排序。 
    特性:stable sort、Out-place sort。 
    最坏情况运行时间:O((n+k)d) 
    最好情况运行时间:O((n+k)d)

    当d为常数、k=O(n)时,效率为O(n) 
    我们也不一定要一位一位排序,我们可以多位多位排序,比如一共10位,我们可以先对低5位排序,再对高5位排序。 
    引理:假设n个b位数,将b位数分为多个单元,且每个单元为r位,那么基数排序的效率为O[(b/r)(n+2^r)]。 
    当b=O(nlgn),r=lgn时,基数排序效率O(n)

    比如算法导论习题8.3-4:说明如何在O(n)时间内,对0~n^3-1之间的n个整数排序? 
    答案:考虑n个三位数(即d=3)的基数排序,每个数字在0~n-1区间(即k=n)。总共有三次调用计数排序,每次花费O(n+k)=O(n+n)=O(n)时间,因此总时间为O(n)。

    这里写图片描述

    九、桶排序

    假设输入数组的元素都在[0,1)之间。 
    特性:out-place sort、stable sort。 
    最坏情况运行时间:当分布不均匀时,全部元素都分到一个桶中,则O(n^2),当然[算法导论8.4-2]也可以将插入排序换成堆排序、快速排序等,这样最坏情况就是O(nlgn)。 
    最好情况运行时间:O(n)

    桶排序的例子: 
    这里写图片描述 
    伪代码: 
    这里写图片描述

    证明算法正确性:

    对于任意A[i]<=A[j],且A[i]落在B[a],A[j]落在B[b],我们可以看出a<=b,因此得证。




    展开全文
  • 为了解决Web数据库多查询结果问题,提出了一种基于上下文偏好的查询结果Top-<em>k排序方法。首先提出了一种带偏好程度的上下文偏好模型:<em>i</em>1 <em>i</em>2, <em>d</em> | <em>X,表示在上下文条件<em>X下,项...
  • 题目:分析求解topk(big)问题时 堆排序 和 快速排序 的使用场景 快速排序求解 &nbsp; &nbsp; &nbsp; &nbsp;这种算法利用了快速排序的主要思想:每次调用快速排序的partition函数后将会得出一个数n...
  • 在grafana 中使用 topk(10, bps) 语句,结果得到如图信息,并且可以看到曲线有断层,不连贯。 期望是仅展示前10条,并且曲线是连贯的。 原因分析: 从Grafana 5.3.0开始,有一个功能允许在一段时间内正确绘制前N...
  • torch.topk(input, k, dim=None, largest=True, sorted=True, out=None) -> (Tensor, LongTensor) input:一个tensor数据 k:指明是得到前k个数据以及其index dim: 指定在哪个维度上排序, 默认是最后一个维度 ...
  • leetcode之TopK算法

    千次阅读 2020-09-10 16:22:40
    leetcode之TopK(快排/堆排序) 快排思想 并不需要把全部都排序好,只用分组快排,快排其实是把小于基准数的所有数放在左边,大于的数都放在右边,只要找到这个基准数在快排后的下标,若下标<k-1,则将左边那组...
  • topK算法常见于排行榜等场景,常规的解法有: 排序 O(nlogn) 对整个数组进行了排序,显然我们只需要前K个,后面的N-K是无意义的排序,有优化空间。 堆 O(nlogk) 建小顶堆,并保持堆中元素个数为k个,遍历一次数组,...
  • Pytorch torch.topk()的简单用法

    千次阅读 2022-02-19 13:56:44
    由于numpy本身是没有提供topk方法的,自己写一个有时候又很蛋疼(懒得写),在这种情况下便可以考虑pytorch提供的topk: torch.topk(input, k, dim=None, largest=True, sorted=True, *, out=None) input:输入...
  • 数据排序TopK问题

    千次阅读 2016-05-27 15:27:51
    【前言】在大规模数据处理中,常遇到的一类问题是,在海量数据中找出出现频率最高的前K个数,或者从海量数据中找出最大的前K个数,这类问题通常称为“topK”问题 【解决思路】 针对topK类问题,通常比较好的方案是...
  • 排序——堆排序TopK

    千次阅读 2019-04-02 10:56:54
    排序TopK的问题,面试中还是经常问的,索性也整理一下。下面是徒手写的,供参考. 堆排序 public void heapSort(int[] array) { // 先构造一个大顶堆 int N = array.length - 1; for (int i = (N - 1) / 2; i ...
  • 海量数据的TopK问题几乎是后台开发面试必备题,本文从排序算法从0优化的角度分析TopK问题的优化。 什么是TopK问题:给定一个很大的数据量n,要求从n中提取出最大/最小/重复频度最高的K个数(K相对于n较小,如n为10亿...
  • 教你用堆排序解决topk问题,同时学会堆排序。 1、什么是Top K问题? 找到数组中最大(最小)的K个数,例如7,6,3,5,2,Top3 的意思就是 找出最小的三个数即为:3,5,2。 方法1:对数组全部排序,然后根据要求取其中K...
  • 排序TopK问题

    千次阅读 2017-05-23 12:28:12
    topK问题是生活中很常见的问题;比如找到N个在某个科目成绩最好的同学,或者在很多游戏中都会有很多数据分析结果,年度评价之列的都是什么游戏时间最长啦,与你开黑时间最多的K个小伙伴啦,都会用到。
  • 1 二叉树的顺序存储 2下标关系 已知父亲节点下标,求孩子节点下表 1 左孩子下标=2*parent+1; ...2 右孩子下标=2*parent+2;...已知孩子节点下表,求父亲节点下标 (不分左右孩子下标) ... 3 满足任意结点的值都大于子树...
  • # i太小了,Topk在右边 return quickSort ( points , i + 1 , hi , k ) elif hi < k + i - 1 : # Topk在左边 return quickSort ( points , lo , i - 1 , k - ( hi - i + 1 ) ) else :...
  • 基于Worker权重差分进化与Top-k排序的结果汇聚算法.docx
  • 【数据结构入门】堆的应用:TopK & 堆排序

    千次阅读 多人点赞 2022-02-28 19:42:00
    文章目录一、Top-k问题1.1 解法一:暴力排序1.2 解法二:建N个数的堆1.3 解法三:建K个数的堆(最优解法)二、堆排序 一、Top-k问题 Top-k问题:在 N 个数中,找出前 K 个(最大/最小)的元素,一般情况下数据量 N ...
  • 排序实现及top-K问题

    千次阅读 2022-04-10 17:33:31
    对于一个任意的数组实现堆排序 方法一:向上调整法 将这个数组看成一个堆,从第二个元素开始进行向上调整直至最后。 即先将前两个元素看成堆,进行向上调整 ...top-K问题 ...TOP-K问题:即求...
  • Tom Zu-search-topK-节省空间 链表实现的Top-K空间节省算法 2021/3 / 4-2021 / 3/5期间完成的工作 论文“数据流中频繁和Top-k元素的有效计算”中提出的算法 链接: : 运行程序 将所有数据放入名称为fname的.txt...
  • TopK问题就像搜索引擎每天会接收大量的用户搜索请求,它会把这些用户输入的搜索关键词记录下来,然后再离线地统计分析,得到最热门的Top10搜索关键词,啥啥惹事就出来了。
  • 实际应用中,我们经常面临这样的问题,即从一个序列S中选择其中最大的K个数(一般情况下K远小于|S|),我们将这种问题称为TopK问题。 举一个例子,美剧《权利的游戏》中的每个人物,观众都会对其进行选择支持或不...
  • TopK优化思路

    2018-09-20 20:00:18
    • 局部排序,只排序TopK个数,O(n*k) • 堆,TopK个数也不排序了,O(n*lg(k)) • 分治法,每个分支“都要”递归,例如:快速排序,O(n*lg(n)) • 减治法,“只要”递归一个分支,例如:二分查找O(lg(n)),随机选择O...
  • 面试 TopK 的五种解法

    2019-07-08 10:06:24
    面试中,TopK,是问得比较多的几个问题之一,到底有几种方法,这些方案里蕴含的优化思路究竟是怎么样的,今天和大家聊一聊。 问题描述: 从arr[1, n]这n个数中,找出最大的k个数,这就是经典的TopK问题。 栗子: ...
  • top K、重复、排序问题

    千次阅读 2018-09-26 15:40:01
    Top K问题:分治+Trie树/Hash_map+小顶堆。采用Hash(x)%M将原文件分割成小文件,如果小文件太大则继续Hash分割,直至可以放入内存。然后使用Trie树来Hash统计每个小数据集中的query词频,之后用小顶堆求出每个数据...
  • 排序 + Top K 问题

    2022-03-15 20:42:40
    [C++][Leetcode][TopK]前K大问题+前K高频(堆+map)_D.Guan的博客-CSDN博客 在大规模数据的时候,快速排序只会线性增长,而堆排序增加幅度很大,会远远大于线性。 堆排序指针寻址会耗费很多...
  • c/c++ 堆排 topk

    2016-08-16 20:39:03
    最大topk 1.建立topk的完全二叉树小根堆 make_heap perc_up:上虑实现 2.迭代判断后续的数字是否大于小根堆的根,如果是,则替换根,并且下滤操作 for (int i = topk; I perc_down() }
  • 大根堆小根堆&TopK问题

    千次阅读 2019-07-28 09:32:46
    大根堆用于升序排序(所以求最小的前k个数用大根堆),小根堆用于降序排序(所以求最大的前k个数(常见的topk问题,基本都是求最大的前k个数)用小根堆)。 堆排序的时间复杂度是O(NlogN),空间复杂度是O(1),所以...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 108,659
精华内容 43,463
关键字:

topk排序