时间复杂度低于空间复杂度的代码是否存在？求反例验证

你的矩阵例子分析是对的，但这个场景里时间和空间复杂度都是O(N²)，属于持平状态，并没有出现空间复杂度高于时间的情况。不过确实存在空间复杂度明显高于时间复杂度的场景，举几个典型的反例：

• 预计算海量结果用于快速查询：比如你需要回答“第k个斐波那契数”的查询，提前把前10^{6个斐波那契数都存在一个数组里。如果只做1次查询，查询操作的时间复杂度是O(1)，但存储这个数组的空间复杂度是O(10}6)，空间复杂度远高于时间复杂度。再比如区间最值查询，提前把所有可能的区间结果存在N×N的二维数组里（空间O(N²)），每次查询直接取值，时间复杂度O(1)，只要查询次数不多，整体空间复杂度就会高于时间。

• 基于哈希表的极端预处理：比如做字符串匹配时，提前把所有长度为5的小写字母子串的哈希值都存在哈希表中（空间复杂度O(26^5)=O(11881376)），每次匹配只需要计算目标子串的哈希值并查表，时间复杂度O(5)=O(1)，这时候空间复杂度远超时间。

• 为极小时间开销牺牲空间的算法：有些加密或数值计算的预处理阶段，会生成一个巨大的查找表（lookup table），后续的核心操作只需要查表就能完成，时间复杂度极低，但查找表的空间复杂度非常高。

总结一下，当我们为了优化单次操作的时间，提前预存储了大量数据，且实际执行的快速操作次数很少时，就会出现空间复杂度远高于时间复杂度的情况。

内容的提问来源于stack exchange，提问作者Aditya Khambete