本文主要记录阅读剑指Offer这本书所遇到的算法解释并作一些个人的拓展，其中的算法面试题请看剑指Offer面试题集

5.2 时间效率

1.细节方面：使用引用(指针)传递复杂类型参数，若采用传值传递参数，从形参到实参会产生一次复制操作

2.实现方式：递归本质是将大的复杂问题分解成小问题解决，若小问题中有重叠部分，则递归时间效率会很差，可采用基于循环+用数组保存中间结果来实现，绝大部分动态规划算法都是分这两个步骤完成

3.数据结构和算法：如查找，不同算法需要的时间效率不同，不同数据结构如哈希表查找的时间不同

5.3时间效率与空间效率的平衡

软件开发中我们允许以牺牲一定空间为代价优化时间性能，尽可能缩短软件响应时间
面试时我们分配少量辅助空间以提高时间效率通常是可以的
如面试题34中用一个数组按照从小到大的顺序保存已经求出的丑数
如面试题43中交替使用两个数组求骰子每个点数出现的次数
但是时间换空间策略并不一定都是可行，如哈希表的空间消耗过大，我们要根据实际情况权衡
如面试题35中数组实现简易哈希表在O(1)查找任意字符，对于ASCII字符总共有256个，因此只需要1K的辅助内存，对于大多数硬件可以接受，但是对于16位的Unicode字符，创建一个长度为2^16的整型数组需要4*2^16就是256K，对于一些嵌入式开发则需要注意

5.4总结

降低时间复杂度的方法有两种
1.改用更高效的算法：如动态规划、快速排序、摩尔投票算法等
2.用空间换时间：如哈希表、递归时有重复子问题可以存储子问题的结果避免重复计算
值得一提的是，空间换取时间不一定可行，注意需要的辅助空间的大小，消耗太多内存可能得不偿失