主题:贪心算法的复杂性问题
设有N个文件f1,f2,…fn,要求存储在一个磁盘上,每个 文件占磁盘上1个磁道,这N个文件的检索概率分别试p1,p2,…pn 而且 n
∑pi =1 。磁头从当前磁道移到被检索信息磁 i=1
道所需的时间可用这两个磁道之间的径向距离来度量。如果文件fi存放在第i道与第j道之间的径向距离。
磁盘文件的最优存储问题要求确定这N个文件在磁盘上的存储位置,使期望检索时间达到最小。试设计一个解决此问题的算法,并分析算法的正确性和计算复杂性。
∑pi =1 。磁头从当前磁道移到被检索信息磁 i=1
道所需的时间可用这两个磁道之间的径向距离来度量。如果文件fi存放在第i道与第j道之间的径向距离。
磁盘文件的最优存储问题要求确定这N个文件在磁盘上的存储位置,使期望检索时间达到最小。试设计一个解决此问题的算法,并分析算法的正确性和计算复杂性。