2

So as I was going through some practice problems from programming contests (ACM ICPC, etc), people can often times take an O(N^2) Solution, or even worse, and use a Heap (priority_queue in C++) or a deque to reduce complexity. (as some sort of optimization, after noticing "something" in the pattern)

For example in the "sliding window maximum" problem, which is pretty much:

For each window of size K in an array of size N, compute the maximum.

There's a trivial O(NK) algorithm, a rather easy O(nlogn) solution (even I can see it, using a heap) and a O(N) solution, using a double ended queue.

These principals seem to be on the principal of "throwing" away useless values, or querying a region to find a property (maximum, cumulative sum, min, etc).

For example to convert some O(N^2) algorithms to O(NlogN), sometimes you can use a priority_queue and keep popping out values until you get one within a certain window, instead of looping through all previous N elements to find a maximum.

Anyone have good tips? (Other than doing more problems... I'm trying to do that)

4

1 回答 1

0

DP算法的基础是分裂问题。

为了降低时间复杂度，让我们以不同的方式拆分问题。

为了体现 DP 算法，我们使用了许多简单的子算法，例如排序、树（即使它不是算法）、...

如果您想降低时间复杂度，请更快地体现此算法。

如果您使用排序，请使用快速排序或堆排序而不是选择/冒泡排序。

如果要获取最小值/最大值，请使用堆或优先级队列。

如果你不能做出更快速的递归公式，那么使用更快速的子算法来减少时间。

于 2012-10-18T09:00:02.057 回答