MENU

算法复杂度分析概要

一:渐近符号

1.1 符号的辨析

1.1.1 符号$O$

$O$,读作“大O”,非正式来说,$O(g(n))$是增长次数小于等于$g(n)$及其常数倍($n$趋向于无穷大)的函数集合。

定义 如果函数$f(n)$包含在$O(g(n))$中,记作$f(n)∈O(g(n))$(平时使用为了方便书写,我们通常使用$f(n)=O(g(n))$代替)。它的成立条件是:对于所有足够大的$n$,$f(n)$的上界由$g(n)$的常数倍所确定,也就是说,存在大于$0$的常数$c$和非负整数$n_0$,使得对于所有的$n≥n_0$来说,$f(n)≤c⋅g(n)$。

下图说明了这个定义:

阅读全文

BFPRT算法(TOP-K问题)

一:背景介绍

在一堆数中求其前k大或前k小的问题,简称TOP-K问题。而目前解决TOP-K问题最有效的算法即是BFPRT算法,又称为中位数的中位数算法,该算法由Blum、Floyd、Pratt、Rivest、Tarjan提出,最坏时间复杂度为$O(n)$。

在首次接触TOP-K问题时,我们的第一反应就是可以先对所有数据进行一次排序,然后取其前k即可,但是这么做有两个问题:

  • 快速排序的平均复杂度为$O(nlogn)$,但最坏时间复杂度为$O(n^2)$,不能始终保证较好的复杂度。
  • 我们只需要前k大的,而对其余不需要的数也进行了排序,浪费了大量排序时间。

除这种方法之外,堆排序也是一个比较好的选择,可以维护一个大小为k的堆,时间复杂度为$O(nlogk)$。

那是否还存在更有效的方法呢?受到快速排序的启发,通过修改快速排序中主元的选取方法可以降低快速排序在最坏情况下的时间复杂度,并且我们的目的只是求出前k,故递归的规模变小,速度也随之提高。下面来简单回顾下快速排序的过程,以升序为例:

(1):选取主元(首元素,尾元素或一个随机元素);
(2):以选取的主元为分界点,把小于主元的放在左边,大于主元的放在右边;
(3):分别对左边和右边进行递归,重复上述过程。

阅读全文