消息提醒-算法设计与分析.pptVIP

消息提醒 160320061 浦佳祺 2016-10-12 问题描述 小w的手机又n个app应用，手机会有三种类型的事件，第一种：app应用x产生了一条未读提醒信息。第二种：小w查看了app应用x的所有提醒信息。第三种：小w查看所有已产生的信息的前t条。 我们需要得到每个事件发生后手机上未读信息的数目。 对问题的理解和分析 对于情况一很好处理，只需要在消息列表里加上新增信息的说明。 对于情况二，我们需要把事件列表中的关于某个app的所有提示信息删除。 对于情况三，我们需要先从消息列表找出对应消息是否已读（比如被情况二），在考虑是否需要标记。 算法与数据结构的选取 算法设计： 根据前面的问题分析，我们看出每步操作都是独立的，所以我根据输入情况分成三种情况对应即可。 数据结构的选取： 我选择了数组来表示消息队列 选择一个向量数组来表示各个app应用消息队列 操作图示 1 2 1 5 4 1 2 3 4 5 1 2 3 4 5 6 7 8 9 10 3 情况一：插入消息事件的操作，插入3号app的未读信息 情况二：删除某个app的未读信息，删除1号app的未读信息 情况三：阅读前t个信息，阅读前5个信息 消息列表 app未读信息列表 核心代码 核心代码 算法复杂度分析 对于情况一：它需要在消息列表和对应app消息列表添加信息，用时O(1)。最多可能有n次。 对于情况二：它需要在app消息列表找出对应app消息并删除，因为用的是数组，用时O(1)。最多也可能有n次。 对于情况三：考虑每次读取前t个，而只有后一次的t大于前一次的t才会执行操作，并且只会读取两次t之间的位置。所以最多只能读取消息队列的总长度n，所以最多需要O(n)时间。而平均每个app下的未读信息为常数k个，所以用时需要O(n)。 综合起来时间为：