求数据流中位数序列的算法分析  

Algorithm analysis on median series calculation of data stream

作　　者：陈文[1] 王琳燕[1] CHEN Wen;WANG Lin-yan(Fnzhon Polytechnic,Fnzhon 350108,China)

机构地区：[1]福州职业技术学院,福州350108

出　　处：《信息技术》2018年第11期34-36,43,共4页Information Technology

基　　金：福建省教育厅中青年教师教育科研项目(JAT171068)

摘　　要：中位数求法通常利用排序算法获取,其时间复杂度达到O(n*ln n)甚至O(n^2)。对于数据流,逐点利用排序法求中位数序列,时间复杂度更高,当数据量很大时,运行极其费时,文中提出利用堆结构获取数据流中位数序列的方法。描述基本思想,分析堆的构造方法,详细介绍算法实现过程。其时间复杂度仅为O(n*ln n),较常用的排序算法有较大的改进。最后,通过实验进一步证实该算法的优越性。Usually,the sorting method is used to get the median,and its time complexity is O（n＊ln n）or even O（n^2）.When the data comes as stream,it need to be calculated a series of median values,and the complexity will be even higher when sorting the array every time,which is time consuming.A method using the heap structure to calculate the median series for a data stream is proposed in this paper which introduces the basic idea of the method,analyzes heap constructing and the process of its implementation in detail.The time complexity is only O（n＊ln n）,which is a considerable improvement of the usual sorting method.Finally,the superiority of the algorithm is confirmed by experiments.

关 键 词：中位数 堆 算法 排序 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]