打表
信息学专用术语
打表,是一个信息学专用术语,意指对一些题目,通过打表技巧获得一个有序表或常量表,来执行程序某一部分,优化时间复杂度。这种算法也可用于在对某种题目没有最优解法时,用来得到分数的一种策略。
打表一般步骤
找到答案的方式
一、通过暴力搜索,找出对于数据的答案,适用于数据较大,题目简单的情况;
二、通过手算,找出每个数据的答案,适用于数据较小且题目较难的情况;
三、在某些题目中,因为考虑到预处理出所有答案的时间复杂度可能会比依次读入再求更优,所以就在读入数据前进行对所有可能的询问的答案或部分必要条件的预处理。这种方法虽然也是打表,但编程复杂度不亚于其他程序,而且一般是题目的正解。
输出答案的方式
一、直接在程序内打表,如果打表复杂度较大则不可用。
二、提前打表,然后复制放入程序。
打表的技巧
1、可把一些相差不大的数据化为与上一段之差:
例如: f[i]储存为f[i]-f[i-1]
输出时以前缀和形式输出。
2、分段打表。
把数据分为几段,每段根据输入数据,找到相应倍数进行输出。
参考资料
最新修订时间:2024-06-26 21:35
目录
概述
打表一般步骤
打表的技巧
参考资料