我有一个名为 get_chapter 的函数，它以页码作为参数并返回一个表示该页面所属章节的唯一字符串，例如“故事继续”。如果我在书外输入页码，则会返回一个空字符串。
第一页是第 0 页。章节是一组连续的页面，给定的页面只属于一个章节。
你会推荐什么算法来识别每一章的页面范围？关于我需要调用 get_chapter 多少次的任何估计？
我需要尽可能限制对 get_chapter 的调用。章节平均 50000 页。这本书大约有30000000页！不知道有多少章。
问问题
34 次
2 回答
2
用第一页填写章节边界列表。
设置low到第一页和high最后一页。
如果get_chapter(low) == get_chapter(high)，那么您知道该范围内的所有内容都在同一章节中，并且您不需要进一步划分它。
如果get_chapter(low) != get_chapter(high)和low + 1 == high，那么您在不同的章节中有相邻的页面。这意味着新的篇章从高处开始。
如果get_chapter(low) != get_chapter(high)和low + 1 < high，则范围内至少有一个章节边界。通过在中间选择一个页面来拆分范围并递归地降低两个新范围（低：中和中：高）。
如果您在找到边界时将边界添加到列表中，并且始终首先递归较低的子范围，那么您就完成了。否则，对边界列表进行排序。
我相信运行时复杂度大约为 O(number_of_chapters * log_2(average_chapter_size))，但这是一个直觉检查而不是彻底的分析。
于 2013-02-14T18:22:43.770 回答
0
一些想法：
在最后一页调用 get_chapter 以查看有多少章。
计算出一章的平均大小，并调用 get_chapter 来估计每章的中间部分。
在相邻章节之间使用二分搜索来找到边界。
针对第 2 步中的初始估计跨越两章或属于同一大章的大章或小章进行修改。
平均调用次数类似于 n + log2(s)，其中 n 是章节数，s 是章节的平均大小（以页为单位）。
于 2013-02-14T14:58:05.863 回答