打表法
tenji edited this page Dec 11, 2023
·
2 revisions
打表是一种典型的用空间换时间的技巧,一般指将所有可能需要用到的结果事先计算出来,这样后面需要用到时就可以直接查表获得。打表常见的用法有如下几种:
这个是最常用到的用法,例如在一个需要查询大量 Fibonacci 数 F(n) 的问题中,显然每次从头开始计算是非常耗时的,对 Q 次查询会产生 O(nQ)
的时间复杂度;而如果进行预处理,即把所有 Fibonacci 数预先计算并存在数组中,那么每次查询就只需 O(1) 的时间复杂度,对 Q 次查询就值需要 O(n+Q)
的时间复杂度(其中 O(n)
是预处理的时间)。
这种用法一般是当程序的一部分过程消耗的时间过多,或是没有想到好的算法,因此在另一个程序中使用暴力算法去算出结果,这样就能直接在源程序中使用这些结果。例如对 N 皇后问题来说,如果使用的算法不够好,就容易超时,而可以在本地用程序计算付出对所有 N 来说 N 皇后问题的方案数,然后把算出的结果直接卸载数组中,就可以根据题目输入的 N 来直接输出结果。
这种用法在数据范围非常大时候容易用到,因为这样的题目可能不是用直接能想到的算法来解决的,而需要寻找一些规律才能得到结果。
动态规划算不算打表法的一种?