时间和空间不可兼得

时间和空间不可兼得"/>

时间和空间不可兼得

鱼和熊掌不能兼得，在算法领域，时间和空间也往往出现不可兼得的情况，需要省时间就要在空间上做些牺牲，要省空间优势就得系统些时间。下面就举一个最近优化算法的实际例子，供以后工作时间中参考。

EXCEL中有2个表格，一个记录历史数据的情况，一个根据当日最新数据计算得到的最新数据。每次历史数据根据当日最新数据计算得到，其中历史数据已经出现的，刷新历史数据；历史数据中没有的进行增加，完成这项工作的2个算法如下。

算法一： 进行2次循环（2个O(n2)）比较；

1. 第一个循环，从历史数据中逐一和最新数据比较，出现过的进行刷新；
2. 第二个循环，从最新数据中和历史数据逐一比较，没有出现过的增加尽历史数据中

算法二：引入一个标志变量，减少第二次循环的算法复杂度

1. 在当日的最新数据中引入一个结构变量，在第一次循环(O(n2))查找后记录是否已经找到，第二次循环O(n)，查找是否已经找到的标志，没有找到的增加近历史记录表格中;