DEFLATE 算法在 RFC 1951 中指定。然而，编码器可以自由选择是插入文字字节，还是为每个输入字节插入输出缓冲区中的子匹配。假设所有内容都通过动态霍夫曼压缩编码在单个块中，那么实现规范允许的最佳压缩比的时间复杂度是多少？
我担心它可能不是多项式，特别是因为 Zopfli 存在（并且他们不声称会产生最佳结果）。然而，我无法找到任何实际的分析或证据来证实这一点。
你的前提有缺陷。单个动态块很少是最佳的。通过适应数据中不断变化的文字、长度和距离分布的多个动态块可以实现更好的压缩。如果块太长，就会损失压缩效率，而压缩效率很容易付出偶尔动态块头来描述新代码的代价。
你的问题也是有缺陷的，如果“时间复杂度”，你的意思是O（未压缩数据长度的某个函数）。我见过的所有放气压缩机都会发出多个尺寸有限的放气块。在这种情况下，时间复杂度为 O(n)，其中 n 是输入长度。
也许您真正想要的是有关 n 前面的常数的信息。该常量可大可小，具体取决于您想要在查找匹配项、选择匹配项以及将它们排列到 deflate 块中投入多少精力。该常数不是时间复杂度。