精华内容
下载资源
问答
  • 实际应用中,我们经常面临这样的问题,即从一个序列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)。

    展开全文
  • 快排2.TOPK版三、复杂度分析 一、TOPK问题 TOPK问题就是在一堆数据里面找到前 K 大的数。 二、算法 1.快排 快排就是把选中的基准数放到它应该在的位置,然后它的左侧的数都比它小,右侧的数都比它大 代码如下(示例...

    一、TOP K问题

    TOP K问题就是在一堆数据里面找到前 K 大的数。

    二、算法

    1.快排

    设输入数组如下
    在这里插入图片描述
    我们把最大的K个数放在后面。

    快排每次把选中的基准数放到它应该在的位置,然后它的左侧的数都比它小,右侧的数都比它大。

    代码如下:

    public static void Sort(int[] a, int l, int r) {
            if (l < r) {//如果l小于r了,说明已经完成这段排序将会直接返回
                int i,j,pivot;
                i = l;
                j = r;
                pivot = a[i];//选择值
                while (i < j) {
                    while(i < j && a[j] > pivot)
                        j--; // 从右向左找第一个小于pivot的数
                    if(i < j)
                        a[i++] = a[j];
                    while(i < j && a[i] < pivot)
                        i++; // 从左向右找第一个大于pivot的数
                    if(i < j)
                        a[j--] = a[i];
                }
                a[i] = pivot; //pivot已被排好序
                Sort(a, l, i-1); /* 递归半区排序 */
                Sort(a, i+1, r); /* 递归半区排序 */
            }
        }
    

    在这里插入图片描述

    2.TOPK版

    TOP K问题中,我们只需要找出最大的几个数,但是不需要对它们进行排序。

    在这里插入图片描述

    比如,我们需要最大的4个数,令k=4。如上图所示,我们的基准数如果一开始恰好就选中了那个本应该排在第七个的数50,那么一次排序后,左侧的数都比50小,得到右侧4个比50大的数,TOP K问题就解决了。

    比起快排,TOP K代码不需要两边都排序,因此在快排基础上只需要加个半区判断即可:

     private static void solution(int[] a, int l, int r,int k) {
            int i=l,j=r,pivot=a[i];
            while (i<j){
                while (i<j&&a[j]>pivot)
                    j--;
                if (i<j)
                    a[i++]=a[j];
                while (i<j&&a[i]<pivot)
                    i++;
                if (i<j)
                    a[j--]=a[i];
            }
            a[i]=pivot;
            if (i==a.length-1-k)
                return;
            else if (i<a.length-1-k)
                solution(a, i+1, a.length-1,k);
            else
                solution(a, 0, i-1,k);
        }
    

    三、复杂度分析

    首先看快排

    最优的时候,每次pivot都恰好选在了中间,两个递归区间长度相同,此时时间复杂度为
    T ( n ) = n + 2 ∗ T ( n 2 ) = n + 2 ∗ ( n 2 ) + 2 ∗ 2 ∗ T ( n 2 ∗ 2 ) + ⋯ + n + T ( 1 ) T ( n ) = n log ⁡ n \begin{gathered} T(n)=n+2 * T\left(\frac{n}{2}\right)=n+2 *\left(\frac{n}{2}\right)+2 * 2 * T\left(\frac{n}{2 * 2}\right)+\cdots+n+T(1) \\ T(n)=n \log n \end{gathered} T(n)=n+2T(2n)=n+2(2n)+22T(22n)++n+T(1)T(n)=nlogn
    最糟糕的时候,每次pivot都选的是排序后最边上的值,这时候的复杂度为
    T ( n ) = n 2 \begin{gathered} T(n)=n ^2 \end{gathered} T(n)=n2
    平均情况下,每种可能性我们都考虑进去,出现的概率为 1 n \frac{1}{n} n1,则复杂度计算公式为
    T ( n ) = n + 1 n ∑ i = 1 n ( T ( i − 1 ) + T ( n − i ) ) T(n)=n+\frac{1}{n} \sum_{i=1}^{n}(T(i-1)+T(n-i)) T(n)=n+n1i=1n(T(i1)+T(ni))
    考虑到和式的对称性, 所以
    T ( n ) = n + 2 n ∑ i = 0 n − 1 T ( i ) T(n)=n+\frac{2}{n} \sum_{i=0}^{n-1} T(i) T(n)=n+n2i=0n1T(i)
    接下来解递推公式得到
    T ( n ) = n log ⁡ n T(n)=n \log n T(n)=nlogn

    接下来分析TOP K下的复杂度

    最好的时候,我们每次选到中间,因为每次选完后只需要对其中一部分进行处理, 因此
    T ( n ) = n + T ( n 2 ) = n + n 2 + 2 ∗ T ( n 2 ) + ⋯ T(n)=n+T\left(\frac{n}{2}\right)=n+\frac{n}{2}+2 * T\left(\frac{n}{2}\right)+\cdots T(n)=n+T(2n)=n+2n+2T(2n)+
    由等比数列求和易知
    T ( n ) = n T(n)=n T(n)=n
    最糟糕的时候, 同样是每次我们都选到了最边上, 这时候每次选择后减少的处理次数也派不上用场,复杂度退化到
    T ( n ) = n 2 T(n)=n^{2} T(n)=n2
    平均情况下,对比快排复杂度计算的式子
    T ( n ) = n + 1 n ∑ i = 0 n − 1 T ( i ) T(n)=n+\frac{1}{n} \sum_{i=0}^{n-1} T(i) T(n)=n+n1i=0n1T(i)
    此时前面的 n \mathrm{n} n 受划分情况的影响,比如,第一次消耗为n,假设第一次刚好选择了中间的值,第二次处理其中一半即可,即 n 2 \frac{n}{2} 2n。假设第一次刚好选择了最边缘的值,第二次还是需要消耗n-1。

    因此前面的 n \mathrm{n} n 受划分情况的影响
    T ( n ) = 1 n ∑ i = 0 n − 1 ( i + T ( i ) ) T(n)=\frac{1}{n} \sum_{i=0}^{n-1}(i+T(i)) T(n)=n1i=0n1(i+T(i))

    T ( n + 1 ) = 1 n + 1 ∑ i = 0 n ( i + T ( i ) ) T(n+1)=\frac{1}{n+1} \sum_{i=0}^{n}(i+T(i)) T(n+1)=n+11i=0n(i+T(i))
    得到
    ( n + 1 ) T ( n + 1 ) − n T ( n ) = T ( n ) + n (n+1) T(n+1)-n T(n)=T(n)+n (n+1)T(n+1)nT(n)=T(n)+n
    这里直接代入法求解就行了
    T ( n ) = n T(n)=n T(n)=n

    展开全文
  • TOPK问题,在一堆无序数组中找到最大或者最小的K个数。一般使用快速排序,然后查找K个数字,时间复杂度最好在nlog,最坏情况O(n2)。而BFPRT算法,又叫做中位数的中位数算法,由五个发明人的名字缩写构成,其最坏的...

            TOPK问题,在一堆无序数组中找到最大或者最小的K个数。一般使用快速排序,然后查找K个数字,时间复杂度最好在nlog,最坏情况O(n2)。而BFPRT算法,又叫做中位数的中位数算法,由五个发明人的名字缩写构成,其最坏的时间复杂度O(n)。

            证明方法参考:这篇文章

            快速排序因为基准点默认选取第一个位置,所以在一定情况下会退化为O(n^2)。bfprt通过修改基准点选择方法,以达到稳定的时间复杂度。

            代码参考上文链接。

    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    /* 对arry[left]...arry[right]进行插入排序(升序) */
    void InsertSort(int arry[], int left, int right)
    {
        for (int i = left + 1; i <= right; i++)
        {
            int j = i;
            while (j - 1 >= left&&arry[j] < arry[j - 1])  //j - 1 >= left避免数组越界
            {
                swap(arry[j - 1], arry[j]);
                j--;
            }
        }
    }
    
    /* 找到中位数的中位数,返回其下标 */
    int FindMidMid(int arry[], int left, int right)
    {
        if (right - left + 1 <= 5)  //如果不足5个
        {
            InsertSort(arry, left, right);
            return (left + right) >> 1;
        }
    
        int j = left - 1;
        for (int i = left; i <= right; i += 5)  //5个一组插入排序取中位数,并统一放在左侧
        {
            InsertSort(arry, i, i + 4);
            swap(arry[++j], arry[i + 2]);
        }
    
        return FindMidMid(arry, left, j);  //直至仅出现一个的中位数
    }
    
    /* 划分,pivot_index为划分基准的下标 */
    int Partion(int arry[], int left, int right, int pivot_index)
    {
        swap(arry[pivot_index], arry[right]);  //把基准放置右侧末尾
    
        int j = left;
        for (int i = left; i < right; i++)  //比基准小的都放在左侧
        {
            if (arry[i] <= arry[right])
                swap(arry[j++], arry[i]);
        }
    
        swap(arry[j], arry[right]);  //最后把基准换回来
        return j;
    }
    
    void BFPRT(int arry[], int left, int right, int k)
    {
        if (left == right)
            return;
        int pivot_index = FindMidMid(arry, left, right);      //找到中位数的中位数的下标,其值作为基准
        int index = Partion(arry, left, right, pivot_index);  //以基准划分
        int num = index - left + 1;
        if (num == k)
            return;
        else if (num > k)
            BFPRT(arry, left, index - 1, k);
        else
            BFPRT(arry, index + 1, right, k - num);
    }
    
    int main()
    {
        int k = 1;
        int arry[10] = { 1,1,2,3,1,5,-1,7,8,-10 };
        BFPRT(arry, 0, 9, k);
    
        for (int i = 0; i < 10; i++)
            cout << arry[i] << " ";
        cout << endl;
        return 0;
    }

     

    展开全文
  • 面试题: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算法,有兴趣的读者可以参看。

    展开全文
  • public static void main(String[] args) { /*start 使用快排找到TopK 时间复杂度大于等于O( k*log(n) ),小于O( n*log(n) ) n为数组长,k为输入的参数 空间复杂度为O(1) */ int k = 7;//从1开始 int[] arr =...
  • 排序算法-堆排序和时间复杂度

    千次阅读 2019-02-16 20:28:04
    假设节点数为n,所以需要进行n - 1次调换,也就是需要n-1次堆调整,每次堆调整的时间复杂度为O(logn) ,那么总的时间复杂度就是(n - 1)O(logn) = O(nlogn) 最后堆排序的时间复杂度为: O(n) + O(nlogn) = O(nlogn)...
  • 算法时间复杂度总结

    千次阅读 2016-08-06 11:52:31
    仅供自己参考- -非常的水,甚至把常数也加进去了所以和网站其他人的不一样 ...从图论的算法开始说说。 Dijkstra点对点最短路: for(i=1;i;i++) { min=MAX; for(j=1;j;j++) { if(!mark[j] && dist[j])
  • Top K算法分析

    万次阅读 多人点赞 2018-10-04 20:35:33
    TopK,是问得比较多的几个问题之一,到底有几种方法,这些方案里蕴含的优化思路究竟是怎么样的,今天和大家聊一聊。 问题描述: 从arr[1, n]这n个数中,找出最大的k个数,这就是经典的TopK问题。 栗子: 从arr[1...
  • title: TopK问题用快排和堆排的复杂度分别是多少? categories: 算法 tags: TopK 关于TopK问题 TopK问题就是在一堆数据里面找到前 K 大(当然也可以是前 K 小)的数 常规方法,完全排序 先完全排序后取topK,这种...
  • 在明白原理后(上一篇讲过),发现朴素算法时间复杂度太大,在找最短的距离需要枚举n个方案,但是在优先队列里面的小跟堆直接找堆顶就行。 优化思路: 用邻接表存图,然后用类似bfs宽搜的原理来更新各个点 代码...
  • 先来聊一聊Top K算法,具体内容如下 应用场景:  搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。  假设目前有一千万个记录(这些查询串的重复度比较高,虽然...
  • 递归算法时间复杂度_递归树

    千次阅读 2017-08-19 19:48:01
    递归算法时间复杂度_递归树
  • 目录 今天也是为了cc,努力奋斗的一天ヾ(≧▽≦*)o 貌似保研面试的时候会问一些这样的问题。。。那我就整理一下吧。反正刷《算法笔记》的时候看见时间复杂度就记到这里呗。 ...
  • TopK算法 排序

    千次阅读 2018-02-23 09:41:09
    amp;fps=1 1、查找最大的k个元素 ...我们知道,快速排序平均所费时间为n*logn,从小到大排序这n个数,然后再遍历序列中后k个元素输出,即可,总的时间复杂度为O(n*logn+k)=O(n*logn)。...
  •  与Dijkstra类似,Prim算法也可以用堆优化,优先队列代替堆,优化的Prim算法时间复杂度O(mlogn)模板(图的存储方式为前向星): void Prim_heap(int point) { memset(dis,0x1f,sizeof(dis)); priority_...
  • (注:总体来说,空间复杂度分析,要不时间复杂度分析难很多,而且空间限制通常比时间限制更难解决)。 排序的前提 传递性:a,b那么a 反自反性,a,那么!(b) 任意2个元素可比较 排序:是一个序列的“逆...
  • 分类:比较排序、非比较排序 比较排序:通过元素间的比较进行排序,时间复杂度不能超过O(nlogn),不在乎数据规模和分布情况。包括:交换(冒泡,快排)、插入(简单插入,...算法复杂度 排序方法 时间复杂度(平...
  • topk算法实现

    千次阅读 2019-03-01 11:07:27
    top k就是求解一个数字队列前k大的问题,在工作后者面试中是一个非常常见的问题,这里说明两种解法。 1.基于快排的解法 1.1 算法思路 这里假设你对快排已经熟悉。我们知道快排是随机找个标识,然后用此标识进行排序...
  • 思路一 利用排序方法(快排/堆... void TopK( int a[], int n, int k ) { if(k&lt;0 || k&gt;n) return; sort(a,n); for(int i=0;i&lt;k;++i) cout&lt;&lt;a[i]&lt;&lt;"...
  • top k算法讲解

    万次阅读 2017-06-22 15:28:55
    在实际工作中,我们时常会有寻找长度为n的数组中,排在前k的元素,对于top k的问题...基于快排的top k算法如果我们了解快速排序算法的话,知道其原理是每次寻找一个数值,将数组中所有小于这个数的值放在其左侧,所有大
  • 1,求最短路的算法和思想: (1)Floyd-Warshal (2)Bellman——ford(求负环) (3)队列优化的Bellman——ford,也就是SPFA(求负环) (4)Dijkstra(不优化&&优化) 2,求最小生成树的算法: 3,求...
  • 算法_时间复杂度

    2020-05-19 10:55:13
    衡量算法优劣的主要标准是时间复杂度和空间复杂度 数据结构:数据的组织、管理和存储格式,其使用目的是为了高效的访问和修改数据 数据结构包含数组、链表这样的线性数据结构,也包含树、图这样的复杂数据结构 ...
  • 八大排序算法复杂度及C++实现

    千次阅读 多人点赞 2020-06-01 12:05:51
    八大排序算法C++代码实现冒泡排序(从小到大)排序原理:优化方法:应用场景:选择排序(从小到大)插入排序(从小到大)希尔排序桶排序堆排序快排序归并排序 冒泡排序(从小到大) 排序原理: 相邻两个值比较大小,...
  • 众所周知常用的图遍历方式有深度优先遍历和广度优先遍历两种,那么我首先来看看这两种算法的具体实现,我们用G[Max][Max]表示图的邻接矩阵。 //三个全局变量 ool Visited[Max];//访问标志 void(*VisFunction)(int ...
  • 时间复杂度为O(n*logn)的排序算法

    千次阅读 2019-07-23 18:20:50
    一、时间复杂度为O(n*logn)的排序算法 二、今日刷题 一、时间复杂度为O(n*longn)的排序算法 1、归并排序: 排序的思想:就是不断分成两部分:左边和右边,分别将左边和右边有序之后才进行合并得到最后的有序的...
  • top-K 算法总结

    千次阅读 2020-09-08 21:21:52
    1000000)个数,求出其中的前K个最小的数(又被称作topK问题) 1 最基本思路 将N个数进行完全排序,从中选出排在前K的元素即为所求。有了这个思路,我们可以选择相应的排序算法进行处理,目前来看快速排序,堆排序和...
  • 算法复杂度分析

    千次阅读 2017-05-03 10:57:50
     我们知道,对于给定的算法我们不仅要考虑数学上的正确性,例如在做基于深度学习的模型时,不仅要通过调参、调整结构等手段使结果满足我们的期望,而且还要讨论其算法复杂度,一般来说有两项内容,【时间复杂度】和...
  • 算法时间复杂度计算

    2015-01-08 19:12:33
    一、概念时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数) 比如:一般总运算次数表达式类似于这样: a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f a ! =0时,时间复杂度就是O(2^n); a=0,bO(n^3); a,b=0,...
  • TopK问题算法详解

    千次阅读 2019-08-09 14:22:26
    面试中,TopK,是问得比较多的几个问题之一,到底有几种方法,这些方案里蕴含的优化思路究竟是怎么样的,今天和大家聊一聊。 画外音:除非校招,我在面试过程中从不问TopK这个问题,默认大家都知道。 问题描述:...
  • java 使用二叉堆实现 TopK 算法

    千次阅读 2017-05-26 20:19:06
    7、算法复杂度的话按top10最坏的情况下,就是每遍历一个数,如果跟堆顶进行替换,需要调整10次的情况,也要比排序速度快,而且也不是把所有的内容全部读入内存,可以理解成就是一次线性遍历. 理论讲完了,下面就是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,753
精华内容 12,301
关键字:

topk算法时间复杂度