单块动态Huffman压缩下最优DEFLATE压缩的时间复杂度是多少？

直接给结论：DEFLATE的最优压缩问题（单块动态Huffman编码场景）是NP难的——除非P=NP成立，否则不存在多项式时间的算法能保证生成符合规范的最优压缩结果。

背后的原因可以拆成两个核心环节来看：

• LZ77匹配决策的复杂度：编码器要为每个输入位置选是输出原文字节，还是选滑动窗口里的子串匹配（用长度+偏移量表示）。这里的关键不是选最长匹配，而是要选能最小化整体编码开销的选项——这个开销还包括后续动态Huffman编码的成本。这类带全局代价约束的序列决策问题，和已被证明为NP难的最短超级串问题、带权路径优化问题本质同源，没法用多项式时间遍历所有可能的最优选择。
• 动态Huffman编码的联动影响：最优Huffman码表的构造完全依赖于LZ77输出的符号（原文字节、匹配长度/偏移量）的频率分布。不同的LZ77决策会彻底改变符号频率，进而改变Huffman编码的开销。这种双向联动让整个问题的复杂度进一步升级，不存在多项式时间的解法。

你提到的Zopfli工具也能佐证这一点：它用的是启发式的迭代贪心策略，通过局部调整来逼近最优结果，但从来不敢宣称能生成全局最优的DEFLATE压缩包——根本原因就是找到真正的最优解需要指数级的时间，在实际场景中完全不具备可行性。

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