algorithm - 动态编程范式是否总是专注于将运行时复杂度限制在 O(n) 内？

Question

我对动态编程的运行时复杂性感到困惑。如果我使用动态编程范式来解决问题，这是否总是 O(n)？

标签： algorithmdynamic-programming

Answer 1

不。

有反例。例如，背包问题有一个动态规划算法，它是 NP 完全的，因此不存在O(n)算法。