设用数组表示一个可清空表,该表支持:add(e) 添加元素e到下一个可用单元格
clear( ) 移除所有元素
这两个操作。现考虑可清空表S上的n个操作序列,当考虑操作之间相互作用后,分析得这一系列操作所需的时间为O(n)
请问这一命题有无实际的举例能帮助理解?以及有无稍详细一点的证明?
命题出自《算法设计与应用》 Michael T.Goodrich Roberto Tamassia[美]著 乔海燕,李悫炜,王烁程译
机械工业出版社 2018年版p21-p22
可清空表上的n个操作需要O(n)的运行时间 如何理解及证明
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
- 拂面清风三点水 2022-01-19 22:35关注
只有不是太严谨的说明:某个具体清空操作时间复杂度为O(1),清空所有的平均时间复杂度为O((1+n)/2)=O(n)
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 拟通过pc下指令到安卓系统,如果追求响应速度,尽可能无延迟,是不是用安卓模拟器会优于实体的安卓手机?如果是,可以快多少毫秒?
- ¥20 神经网络Sequential name=sequential, built=False
- ¥16 Qphython 用xlrd读取excel报错
- ¥15 单片机学习顺序问题!!
- ¥15 ikuai客户端多拨vpn,重启总是有个别重拨不上
- ¥20 关于#anlogic#sdram#的问题,如何解决?(关键词-performance)
- ¥15 相敏解调 matlab
- ¥15 求lingo代码和思路
- ¥15 公交车和无人机协同运输
- ¥15 stm32代码移植没反应