kir*_*off 4 c++ sorting algorithm complexity-theory
我问你关于这个问题的想法:
我有一个数组A,N个元素类型double(或整数).我想找到一个复杂度小于O(N 2)的算法来查找:
max A[i] - A[j]
对于1 <j <= i <n.请注意,没有abs().我想到了:
你有什么意见或想法吗？你能指出一些好的参考资料来训练或进步来解决这样的算法问题吗？
在阵列中进行三次扫描.首先,从目前j=2为止,a用最小元素填充辅助数组.然后,执行从上扫i=n-1下来,填充(也从上向下)另一辅助阵列,b与最大元件迄今(从顶部).现在扫描两个辅助数组,寻找最大的差异b[i]-a[i].
这将是答案.O(n)总共.你可以说这是一个动态规划算法.
编辑:作为一种优化,可以消除第三扫描和第二阵列,并通过维护两个循环变量,发现在第二次扫描答案最多那么远,从最顶部和最大差.
至于"指针"关于如何解决一般这样的问题,你通常会尽量就像你写了一些通用的方法 - 分而治之,记忆化/动态规划等.首先在你的问题和概念涉及仔细一看.在这里,它是最大/最小.将这些概念区分开来,看看这些部分如何在问题的背景下结合,可能改变它们的计算顺序.另一个是在你的问题中寻找隐藏的顺序/对称性.
具体来说,沿着列表固定任意内点k,这个问题被简化为找到所有js中的最小元素之间的差异1<j<=k,以及is:中的最大元素k<=i<n.你在这里看到分而治之,以及拆分max/min的概念(即它们的渐进式计算),以及各部分之间的相互作用.隐藏的顺序显示(k沿着阵列云),和记忆化有助于节省为最大/最小值的临时结果.
任意点的固定k可以被看作是第一个解决一个较小的子问题("为给定的k......"),并查看是否有什么特别之处,它可以取消- 推广 - 抽象了.
还有就是试图制定并首先解决一个更大的问题,使得原来的问题是这样的一个大的一部分的技术.在这里,我们想到找到每个k的所有差异,然后从中找到最大的差异.
中期结果的双重用途(用于比较特定k点,以及计算每个方向的下一个中间结果)通常意味着一些可观的节省.所以,