精华内容
下载资源
问答
  • 写在前面在人工智能算法岗位的面试中,TopK是问得最多的几个问题之一:到底有几种方法?这些方案里蕴含的优化思路究竟是怎么样的?为啥TopK这么受欢迎呢?究其原因,还是因为它不仅在AI领域广泛应用,比如max ...

    e218a129ee175f3184695d74a40e3676.png

    写在前面

    在人工智能算法岗位的面试中,TopK是问得最多的几个问题之一:

    到底有几种方法?

    这些方案里蕴含的优化思路究竟是怎么样的?

    为啥TopK这么受欢迎呢?究其原因,还是因为它不仅在AI领域广泛应用,比如max pooling,mAP计算等;还涵盖了算法专业的很多必备知识,比如快速排序,二分查找,分治减治,大小顶堆等;一些适当的变换,还可以考察应聘者的思维灵活度。

    下面的文章转自架构师之路,是笔者见过此类文章中总结的最透彻的一篇,为了行文流畅,文章有增删。

    正文

    问题描述:

    从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个。

    一、排序

    c6c6c35bb7089f71cd175f288f5d01a8.png

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

    伪代码:

    sort(arr, 1, n);

    return arr[1, k];

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

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

    二、局部排序

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

    056583e6f42de970f6a45aefb9e1ceb9.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。

    9e1b463e5d4df6acc42b508ac278d8af.png

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

    cfdbaf14b8a75a83c5dcd09dfe992d98.png

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

    5076d2c5d7955402cf588177bbf3ffee.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),是一个线性复杂度的方法。

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

    画外音:

    (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是划分元素

    ab4df2f33b4d05736c86b9653976868b.png

    以上述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大

    }

    e91edb3683c2f1a9c86cf344e95db159.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有新的认识。

    ---------------------

    原文链接:https://blog.csdn.net/z50L2O08e2u4afToR9A/article/details/82837278

    更多内容,欢迎关注微信公众号:BloomCV“计算视觉与深度学习的小屋”

    展开全文
  • 面试题:top k算法O(n)时间复杂度

    千次阅读 2015-02-04 11:34:15
    在《数据结构与算法分析--c语言描述》一书,第7章第7.7.6节中,阐述了一种在平均情况下,时间复杂度为O(N)的快速选择算法。如下述文字: 选取S中一个元素作为枢纽元v,将集合S-{v}分割成S1和S2,就像快速排序...

    在《数据结构与算法分析--c语言描述》一书,第7章第7.7.6节中,阐述了一种在平均情况下,时间复杂度为O(N)的快速选择算法。如下述文字:

    • 选取S中一个元素作为枢纽元v,将集合S-{v}分割成S1和S2,就像快速排序那样
      • 如果k <= |S1|,那么第k个最小元素必然在S1中。在这种情况下,返回QuickSelect(S1, k)。
      • 如果k = 1 + |S1|,那么枢纽元素就是第k个最小元素,即找到,直接返回它。
      • 否则,这第k个最小元素就在S2中,即S2中的第(k - |S1| - 1)个最小元素,我们递归调用并返回QuickSelect(S2, k - |S1| - 1)。

    此算法的平均运行时间为O(n)。

    示例代码如下:

    //QuickSelect 将第k小的元素放在 a[k-1]  
    void QuickSelect( int a[], int k, int left, int right )
    {
        int i, j;
        int pivot;
    
        if( left + cutoff <= right )
        {
            pivot = median3( a, left, right );
            //取三数中值作为枢纽元,可以很大程度上避免最坏情况
            i = left; j = right - 1;
            for( ; ; )
            {
                while( a[ ++i ] < pivot ){ }
                while( a[ --j ] > pivot ){ }
                if( i < j )
                    swap( &a[ i ], &a[ j ] );
                else
                    break;
            }
            //重置枢纽元
            swap( &a[ i ], &a[ right - 1 ] );  
    
            if( k <= i )
                QuickSelect( a, k, left, i - 1 );
            else if( k > i + 1 )
                QuickSelect( a, k, i + 1, right );
        }
        else  
            InsertSort( a + left, right - left + 1 );
    }
    

    这个快速选择SELECT算法,类似快速排序的划分方法。N个数存储在数组S中,再从数组中选取“中位数的中位数”作为枢纽元X,把数组划分为Sa和Sb俩部分,Sa<=X<=Sb,如果要查找的k个元素小于Sa的元素个数,则返回Sa中较小的k个元素,否则返回Sa中所有元素+Sb中小的k-|Sa|个元素,这种解法在平均情况下能做到O(n)的复杂度。

    更进一步,《算法导论》第9章第9.3节介绍了一个最坏情况下亦为O(n)时间的SELECT算法,有兴趣的读者可以参看。

    展开全文
  • 实际应用中,我们经常面临这样的问题,即从一个序列S中选择其中最大的K个数(一般情况下K远小于|S|),我们将这种问题称为TopK问题。 举一个例子,美剧《权利的游戏》中的每个人物,观众都会对其进行选择支持或不...

    一、背景

           实际应用中,我们经常面临这样的问题,即从一个序列S中选择其中最大的K个数(一般情况下K远小于|S|),我们将这种问题称为TopK问题。

           举一个例子,美剧《权利的游戏》中的每个人物,观众都会对其进行选择支持或不支持,这样每个人物都会都应一个热度值,这个值可以是支持者的数量,我们可以发现在腾讯视频中该剧中热度排名前3的人物加以了高亮标识,如下图:

        诸如此类的应用场景很多,本文借助快速排序的思想,给出解决此问题的一个时间复杂度为O(N)的算法。

    二、快速排序思想

        为了引出本文基于快排TopK的思想,先给出快排的算法描述,令S为待排序集合,|S|表示集合元素数量。

        1、如果 S 中元素个数是0或1,则返回。

        2、取 S 中任一元素 v, 称之为枢纽元。

        3、将 S - {v} (S中其余元素) 分成两个不相交的集合:S_1 = \left \{ x \in S - \left \{ v \right \} | x\leqslant v\right \}S_2 = \left \{ x \in S - \left \{ v \right \} | x\geqslant v\right \}

        4、返回 {quicksort(S_1)后,继随 v, 继而quicksort(S_2) }。

        本人博客https://blog.csdn.net/gaoxueyi551/article/details/46778181中的代码便是该思想的实现,可供参考。

     

    三、基于快速排序的TopK算法

         其实,只要稍加修改快排算法,即可实现平均时间复杂度为O(N)的TopK算法,我们称之为QuickSelect(S, K)。

         1、如果|S| = 1,返回S,否则若|S| < 20,则使用选择排序对S排序,选择最大的K个元素返回

         2、选取一个枢纽元 v 属于 S。(同快速排序步骤2

         3、将集合 S - {v} 分割成 S1 和 S2。 (同快速排序步骤3

         4、如果K <= |S1| ,则K个元素必然全部位于集合S1中,并返回QuickSelect(S1, K);如果K = |S1| + 1,则集合S1 与 枢纽元 v 恰好是所求的K个数,我们将 S1 和 v 一并返回;如果K > |S1| + 1,那么S1和枢纽元v必然是K个元素的一部分,剩余K - |S1| - 1 个元素必然存在集合 S2 中,因此我们应该返回 S1 + v + QuickSelect(S2, K - |S1| - 1)。

        仔细分析该算法可得如下结论:

    •   快速选择算法的递归调用次数是快速排序的一半。
    •   两种算法的最坏情形都是O(N*N),即集合已排序的情况。
    •   算法平均时间复杂度为O(N)。

         结论2易于理解。分析算法可知,每一轮递归开始之前,我们已经消去了1个集合,递归仅作用在另外一个集合,结论2于是成立。结论3的推导依赖结论1。

         在理想情况下,枢纽元 v 的选择使每轮递归都近似的将当前集合等分,故最多需要递归O(logN)次:

             第1次递归对应的集合长度为 |S / 2|,

             第2次递归对应的集合长度为 |S / 4|,

             第3次递归对应的集合长度为 |S / 8|,

             ......

             第log(N) 次递归对应的集合长度为 1,

         将O(logN)次递归的集合长度相加,

             Sum = |S / 2| + |S / 4| + |S / 8| + ...... + 1

         这是等比数列,根据等比数列求和方法可得Sum大约等于2N,故快速选择的平均时间复杂度为O(N)。

    展开全文
  • 堆基本概念堆排序是一个很重要的排序算法,它是高效率的排序算法,复杂度是O(nlogn),堆排序不仅是面试进场考的重点,而且在很多实践中的算法会用到它,比如经典的TopK算法、小顶堆用于实现优先级队列。堆排序是利用...

    原创文章出自公众号:「码农富哥」,欢迎转载和关注,如转载请注明出处!

    堆基本概念

    堆排序是一个很重要的排序算法,它是高效率的排序算法,复杂度是O(nlogn),堆排序不仅是面试进场考的重点,而且在很多实践中的算法会用到它,比如经典的TopK算法、小顶堆用于实现优先级队列。

    堆排序是利用堆这种数据结构所设计的一种排序算法。堆实际上是一个完全二叉树结构。

    问:那么什么是完全二叉树呢?

    答:假设一个二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

    我们知道堆是一个完全二叉树了,那么堆又分两种堆:大顶堆 和 小顶堆

    它们符合一个重要的性质:

    小顶堆满足: Key[i] <= key[2i+1] && Key[i] <= key[2i+2]

    大顶堆满足: Key[i] >= Key[2i+1] && key >= key[2i+2]

    怎么理解呢,其实很简单,顾名思义,大顶堆最大的元素在跟节点,堆的性质决定了大顶堆中节点一定大于等于其子节点,反之,小顶堆的最小元素在根节点。我们来看看大顶堆和小顶堆的示意图:

    堆排序基本思想及步骤

    堆排序有以下几个核心的步骤:

    将待排序的数组初始化为大顶堆,该过程即建堆。

    将堆顶元素与最后一个元素进行交换,除去最后一个元素外可以组建为一个新的大顶堆。

    由于第二部堆顶元素跟最后一个元素交换后,新建立的堆不是大顶堆,需要重新建立大顶堆。重复上面的处理流程,直到堆中仅剩下一个元素。

    假设我们有一个待排序的数组 arr = [4, 6, 7, 2, 9, 8, 3, 5], 我们把这个数组构造成为一个二叉树,如下图:

    问:此时我们需要把这个完全二叉树构造成一个大顶堆,怎么构造呢?

    答:一个很好的方法是遍历二叉树的非叶子节点自下往上的构造大顶堆,针对每个非叶子节点,都跟它的左右子节点比较,把最大的值换到这个子树的父节点。

    问:为什么要从非叶子节点开始,而不是从最后一个节点开始?

    答:因为叶子节点下面没有子节点了,就没必要操作了。

    问:为什么要从下往上而不是从上往下遍历非叶子节点?

    答:我们从下面开始遍历调整每个节点成为它左右节点的最大值,那么一直往上的话,最后根节点一定是最大的值;但是如果我们从上往下,上面满足了大顶堆,下面不满足,调整后,上面可能又不满足了,所以从下往上是最好的方案。

    那么我们构造的大顶堆的代码就很明显了:

    # 构造大顶堆,从非叶子节点开始倒序遍历,因此是l//2 -1 就是最后一个非叶子节点

    l = len(arr)

    for i in range(l//2-1, -1, -1):

    build_heap()

    # 遍历针对每个非叶子节点构造大顶堆

    看我们的例子,非叶子节点有2, 8, 6, 4, 我们从最后一个非叶子节点,也就是5开始遍历构造大顶堆,2 跟 5 比较,5比较大,所以把 arr[3]和arr[7]从数组中交换一下位置,那么就完成第一个非叶子节点的置换。下面的节点继续交换

    此时9跟4交换后,4这个节点下面的树就不是不符合大顶堆了,所以要针对4这个节点跟它的左右节点再次比较,置换成较大的值,4跟左右子节点比较后,应该跟6交换位置。

    那么至此,整个二叉树就是一个完完整整的大顶堆了,每个节点都不小于左右子节点。

    此时我们把堆的跟节点,即数组最大值9跟数组最后一个元素2交换位置,那么9就是排好序的放在了数组最后一个位置

    2到了跟节点后,新的堆不满足大顶堆,我们需要重复上面的步骤,重新构造大顶堆,然后把大顶堆根节点放到二叉树后面作为排好序的数组放好。就这样利用大顶堆一个一个的数字排好序。

    值得注意的一个地方是,上面我们把9和2交换位置后,2处于二叉树根节点,2需要跟右子树8交换位置,交换完位置后,右子树需要重新递归调整大顶堆,但是左子树6这边,已经是满足大顶堆属性,因为不需要再操作。

    我们再看看堆排序的一个直观的动图吧:

    代码实现:

    class Solution(object):

    def heap_sort(self, nums):

    i, l = 0, len(nums)

    self.nums = nums

    # 构造大顶堆,从非叶子节点开始倒序遍历,因此是l//2 -1 就是最后一个非叶子节点

    for i in range(l//2-1, -1, -1):

    self.build_heap(i, l-1)

    # 上面的循环完成了大顶堆的构造,那么就开始把根节点跟末尾节点交换,然后重新调整大顶堆

    for j in range(l-1, -1, -1):

    nums[0], nums[j] = nums[j], nums[0]

    self.build_heap(0, j-1)

    return nums

    def build_heap(self, i, l):

    """构建大顶堆"""

    nums = self.nums

    left, right = 2*i+1, 2*i+2 ## 左右子节点的下标

    large_index = i

    if left <= l and nums[i] < nums[left]:

    large_index = left

    if right <= l and nums[left] < nums[right]:

    large_index = right

    # 通过上面跟左右节点比较后,得出三个元素之间较大的下标,如果较大下表不是父节点的下标,说明交换后需要重新调整大顶堆

    if large_index != i:

    nums[i], nums[large_index] = nums[large_index], nums[i]

    self.build_heap(large_index, l)

    堆排序复杂度

    时间复杂度, 包括两个方面:

    初始化建堆过程时间:O(n)

    更改堆元素后重建堆时间:O(nlogn),循环 n -1 次,每次都是从根节点往下循环查找,所以每一次时间是 logn,总时间:logn(n-1) = nlogn - logn ,所以复杂度是 O(nlogn)

    时间复杂度:O(nlogn)

    空间复杂度: 因为堆排序是就地排序,空间复杂度为常数:O(1)

    堆排序的应用:TopK算法

    面试中经常考的一个面试题就是,如果在海量数据中找出最大的100个数字,看到这个问题,可能大家首先会想到的是使用高效排序算法,比如快排,对这些数据排序,时间复杂度是O(nlogn),然后取出最大的100个数字。但是如果数据量很大,一个机器的内存不足以一次过读取这么多数据,就不能使用这个方法了。

    不使用分布式机器计算,使用一个机器也能找出TopK的经典算法就是使用堆排序了,具体方法是:

    维护一个大小为 K 的小顶堆,依次将数据放入堆中,当堆的大小满了的时候,只需要将堆顶元素与下一个数比较:

    如果小于堆顶元素,则直接忽略,比较下一个元素;

    如果大于堆顶元素,则将当前的堆顶元素抛弃,并将该元素插入堆中。遍历完全部数据,Top K 的元素也自然都在堆里面了。

    整个操作中,遍历数组需要O(n)的时间复杂度,每次调整小顶堆的时间复杂度是O(logK),加起来就是 O(nlogK) 的复杂度,如果 K 远小于 n 的话, O(nlogK) 其实就接近于 O(n) 了,甚至会更快,因此也是十分高效的。

    总结

    堆排序有以下几个核心的步骤:

    将待排序的数组初始化为大顶堆,该过程即建堆。

    将堆顶元素与最后一个元素进行交换,除去最后一个元素外可以组建为一个新的大顶堆。

    由于第二部堆顶元素跟最后一个元素交换后,新建立的堆不是大顶堆,需要重新建立大顶堆。重复上面的处理流程,直到堆中仅剩下一个元素。

    最后

    文章如果对你有收获,可以收藏转发,这也是对我写作的肯定!另外可以关注我公众号「码农富哥」 ,我会持续输出Python,服务端架构,计算机基础(MySQL, Linux,TCP/IP)的 原创 文章

    展开全文
  • 而BFPRT算法,又叫做中位数的中位数算法,由五个发明人的名字缩写构成,其最坏的时间复杂度O(n)。 证明方法参考:这篇文章 快速排序因为基准点默认选取第一个位置,所以在一定情况下会退化为O(n^2)。bfpr...
  • TopK算法性能对比从arr[1, n]这n个数中,找出最大的k个数,这就是经典的TopK问题。 笔者将 使用冒泡算法和小顶堆实现TopK,对比其时间复杂度。冒泡算法实现不需要将数据全部排序,只用排k轮即可。import java.util....
  • 时间复杂度:O(n^2)选择排序:每次在无序队列中“选择”出最大值,放到有序队列的最后,并从无序队列中去除该值(具体实现略有区别)。时间复杂度:O(n^2)直接插入排序:始终定义第一个元素为有序的,...
  • java top k_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个数排序...
  • Topk算法

    2021-03-22 21:52:38
    topK算法 思路1: 可以采用快速选择算法,借助快排,设mid为每次划分中间结果,每次划分完之后如果mid==k,则说明序列刚刚好,第k位置和他前面的位置都是前K大的数,如果mid < k,则说明第K大的元素在后半部分,则...
  • topk算法

    2020-08-06 22:02:17
    1.首先读入前100个数,用最小堆排序,时间复杂度为O(klogk)(k为数组的大小即为100)。 2.然后遍历后续的数字,并于堆顶(最小)数字进行比较。如果比最小的数小,则继续读取后续数字;如果比堆顶数字大,则替换堆...
  • Top K算法

    千次阅读 2017-03-25 20:27:04
    我们知道,快速排序平均所费时间为n*logn,从小到大排序这n个数,然后再遍历序列中后k个元素输出,即可,总的时间复杂度为O(n*logn+k)=O(n*logn)。 2、排序,选择排序。用选择或交换排序,即遍历n个数,先把...
  • top k算法讲解

    2018-07-10 22:48:55
    排在前k的元素,对于top k的问题,最暴力的处理方式就是直接对数组进行排序,然后再去截取前k个数字,从而达到自己的目的,这种算法的实现复杂度为O(nlogn),其实有O(n)的算法或者是O(nlogk)时间复杂度算法...
  • Top K 问题相信大家在面试过程中,经常被问到,下面就和大家一起探讨下两种常见的算法实现。...算法优势  时间复杂度是O(N*logK),不需要将数组一次全部加载到内存中,可以处理海量数据。图解TopK-堆排序法代码...
  • 堆基本概念堆排序是一个很重要的排序算法,它是高效率的排序算法,复杂度是O(nlogn),堆排序不仅是面试进场考的重点,而且在很多实践中的算法会用到它,比如经典的TopK算法、小顶堆用于实现优先级队列。堆排序是利用...
  • Top K 算法详解

    2016-09-05 11:55:39
     不难分析出,这样,算法的最坏时间复杂度是N*K, 其中K是指top多少。  算法三:堆  在算法二中,我们已经将时间复杂度由NlogN优化到N*K,不得不说这是一个比较大的改进了,可是有没有更好的办法呢?  分析...
  • 堆排序是一个很重要的排序算法,它是高效率的排序算法,复杂度是O(nlogn),堆排序不仅是面试进场考的重点,而且在很多实践中的算法会用到它,比如经典的TopK算法、小顶堆用于实现优先级队列。 堆排序是利用堆这种...
  • 堆排序法来解决N个数(非常大)中的TopK的思路是: 1、先随机取出N个数中的K个数,将这N个数构造为小顶堆,那么堆顶的数肯定就是这K个数中最小的数了。 2、然后再将剩下的N-K个数与堆顶进行比较,如果大于堆顶,那么...
  • Top K算法和寻找第K个最小的数

    千次阅读 2016-01-19 19:34:46
    关于Top K算法和寻找第K个最小的数这种经典问题网上已经说的很详细了,不过毕竟不是自己的,这里自己总结一下,而且这两个问题又稍稍有点区别。 1.Top K算法:即寻找一列数中K个最小值或K个最大值,这里仅以寻找K个...
  • TopK算法 排序

    千次阅读 2018-02-23 09:41:09
    amp;fps=1 1、查找最大的k个元素 ...我们知道,快速排序平均所费时间为n*logn,从小到大排序这n个数,然后再遍历序列中后k个元素输出,即可,总的时间复杂度为O(n*logn+k)=O(n*logn)。...
  • TopK算法,用于寻找若干个数据中最大或最小的K个数。 实现TopK有两种方法,一种是基于快排的思想,一种是基于堆排的思想。 他们区别在于: 快排:时间复杂度O(n) 需要修改输入数组 不能处理海量数据,因为内存不够...
  • 总的来说,方法和时间复杂度如下: 全局排序,O(n*lg(n)) 局部排序,只排序TopK个数,O(n*k) 堆,TopK个数也不排序了,O(n*lg(k)) 分治法,每个分支“都要”递归,例如:快速排序,O(n*lg(n)) 减治法,“只要”递归...
  • [面试]TopK算法解析

    2019-01-29 21:37:15
    解法一 ...总的时间复杂度为O(N*logN)+O(K)=O(N*logN)。该算法存在以下问题: 快速排序的平均复杂度为O(N*logN),但最坏时间复杂度为O(n2),不能始终保证较好的复杂度 只需要前k大或k小的数,,...
  • 海量数据:TopK算法

    2020-02-11 11:22:48
    找出无序数组中第K大的元素(前K大元素) 方法一:堆排序 ...时间复杂度:O(klogk + (n-k)logk) = O(nlogk) 空间复杂度:O(k), 当然也可以不开辟空间,也就是O(1) //调整为最小堆 void heapAdjust(ve...
  • Top K算法问题的实现

    千次阅读 2014-07-14 10:37:23
    在上一篇文章,程序员面试题狂想曲:第三章、寻找最小的k个数中,后来为了论证类似快速排序中partition的方法在最坏情况下,能在O(N)的时间复杂度内找到最小的k个数,而前前后后updated了10余次。所谓功夫不负苦心...
  • 1. 堆算法Top时间复杂度 O(LogN)function top(arr,comp){ if(arr.length == 0){return ;} var i = arr.length / 2 | 0 ; for(;i >= 0; i--){ if(comp(arr[i], arr[i * 2])){exch(arr, i, i*2);} if(comp(arr[i]...
  • 构建堆的时间复杂度

    万次阅读 2017-02-26 19:11:41
    大顶堆、小顶堆是一种很常用的数据结构,例如常见的堆排序和topk算法,在很多应用场景中,我们经常会关注算法时间复杂度和空间复杂度,众所周知构建堆的时间复杂度是o(n),那么为什么是o(n)?本文主要跟大家讨论下这...
  • 常用的排序算法包括: ...时间复杂度:O(n^2) 选择排序:每次在无序队列中“选择”出最大值,放到有序队列的最后,并从无序队列中去除该值(具体实现略有区别)。时间复杂度:O(n^2) 直接插入排序:始终定义第一...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 262
精华内容 104
关键字:

topk算法时间复杂度