数据流序列去掉最值的算法分析

摘要

线性顺序存储下求n个数据最大值,时间复杂度为O(n).在数据流序列下,维护最大值的时间复杂度为O(n^2).本文提出利用二叉排序树维护数据最大值的方法.在理想状况下,该方法的时间复杂度为O(n*ln(n)).本文首先分析算法的实现原理及具体的实现方法,并用实例对比验证算法的有效性,最后提出算法的改进措施及应用扩展.