goo*_*cow 2 sorting algorithm dynamic-programming
动态规划问题具有最优子结构,并且具有可以通过递归关系描述的解决方案.
排序列表是向已排序列表添加元素,因此插入排序具有最佳子结构.递归关系可以描述为
Sorted_List_n = Sorted_list_n-1 + next element
那么为什么插入排序不被认为是动态编程算法呢？我理解它是如何应用于斐波纳契数和编辑距离的,但并不是真的超出了它.
如果问题具有以下两个属性,则可以使用动态编程(DP)解决给定问题.
1)重叠子问题(osp)
2)最优子结构(oss)
尽管插入排序算法具有最佳子结构属性,但它没有重叠的子问题属性.有点详细解释如下..
在Fibonacci数计算的情况下,我们显然具有上述两个属性.
osp: fib(5)计算有fib(3)作为其子问题.同时,fib(4)计算有fib(3)作为其子问题.但是fib(5)= fib(4)+ fib(3).如果我们用DP技术盲目地计算fib(5),我们最终计算两次fib(3)(一个用于fib(4),一个用于fib(3)本身).这里,重叠的子问题之一是fib(3)
oss:以同样的方式,如果我们能够最优地计算fib(4)和fib(3)的解,那么也可以最佳地计算fib(5)的解.因为fib(5)仅仅是fib(4)和fib(3)的总和.
现在,让我们尝试检查插入排序中是否存在这两个属性.我们假设你正在排序一组数字{5,2,3,1}.
osp:根据您认为子问题的复发情况如下:
{5,2,3,1}
{5,2,3}
{5,2}
{5}
如果仔细观察,我们可以看到没有两个相似的子问题.这意味着重叠的子问题属性不存在.
oss:如果我们可以最佳地对大小(n-1)的数组进行排序,那么我们也可以最佳地对大小(n)的数组进行排序.因此存在最佳子结构属性.
总之,插入排序算法没有重叠的子问题属性.因此,它不是DP解决方案.