打表(信息學專用術語)

打表，是一個信息學專用術語，意指對一些題目，通過打表技巧獲得一個有序表或常量表，來執行程式某一部分，最佳化時間複雜度。這種算法也可用於在對某種題目沒有最優解法時，用來得到分數的一種策略。

基本介紹

• 中文名：打表
• 外文名：Make Charts
• 概念：手算出一個有序表或常量表來最佳化程式時間複雜度
• 用途：OI競賽

打表一般步驟

找到答案的方式

一、通過暴力搜尋，找出對於數據的答案，適用於數據較大，題目簡單的情況；

二、通過手算，找出每個數據的答案，適用於數據較小且題目較難的情況；

三、在某些題目中，因為考慮到預處理出所有答案的時間複雜度可能會比依次讀入再求更優，所以就在讀入數據前進行對所有可能的詢問的答案或部分必要條件的預處理。這種方法雖然也是打表，但編程複雜度不亞於其他程式，而且一般是題目的正解。

輸出答案的方式

一、直接在程式內打表，如果打表複雜度較大則不可用。

二、提前打表，然後複製放入程式。

直接帶入數據的打表占用空間大

打表的技巧

1、可把一些相差不大的數據化為與上一段之差：

例如： f[i]儲存為f[i]-f[i-1]

輸出時以前綴和形式輸出。

2、分段打表。

把數據分為幾段，每段根據輸入數據，找到相應倍數進行輸出。