算法导论思考题 18-1_算法导论18-1

作者：你好赵伟 | 2024-04-07 01:12:19

踩

算法导论18-1

a. 最坏情况下，n个栈操作需要O(n)次磁盘存取，由题目可知，每次存取需要O(m)cpu时间，所以一共需要O(mn)的cpu时间

b. 内存中如果有一页的缓存，就可以存m个字。所以最坏情况n个push需要进行O(n/m)次磁盘存取，需要O(n/m)*O(m)=O(n)cpu时间，

c. 最坏情况，设页面是满的，push,pop,pop,push,push,pop,pop......n个栈操作需要O(n)次磁盘存取，需要O(mn)的cpu时间

d. 缓存最近使用的两页。

假设内存中有n1n2两页，并且都已经满了，再次执行push操作，将n1写进磁盘，读入n3，执行push，这时内存中是n2n3

假设内存中有n1n2两页，并且都为空，再次执行pop操作，将n2写进磁盘，读入n0，执行pop，这时内存中是n0n1

其余时间，都在内存中操作，不存取磁盘

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/375463?site

算法导论 思考题 18-1_算法导论18-1