䶛饆䟁礥 2022-01-19 20:45 采纳率: 100%
浏览 10
已结题

可清空表上的n个操作需要O(n)的运行时间 如何理解及证明

设用数组表示一个可清空表，该表支持：add(e) 添加元素e到下一个可用单元格
clear( ) 移除所有元素
这两个操作。现考虑可清空表S上的n个操作序列，当考虑操作之间相互作用后，分析得这一系列操作所需的时间为O(n)
请问这一命题有无实际的举例能帮助理解？以及有无稍详细一点的证明？
命题出自《算法设计与应用》 Michael T.Goodrich Roberto Tamassia[美]著 乔海燕，李悫炜，王烁程译
机械工业出版社 2018年版p21-p22

  • 写回答

1条回答 默认 最新

  • 拂面清风三点水 2022-01-19 22:35
    关注

    只有不是太严谨的说明：某个具体清空操作时间复杂度为O(1)，清空所有的平均时间复杂度为O((1+n)/2)=O(n)

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题？

问题事件

  • 系统已结题 3月25日
  • 已采纳回答 3月17日
  • 创建了问题 1月19日