通过一种算法降低 [英] Decrease by one algorithm

问题描述

如果减少了由一个策略的定义是：

If the definition of a decrease by one strategy is:

的策略，其中所要解决的问题的大小平稳降低通过在每个迭代一个元素。

"A strategy where the size of the problem to be solved is steadily decreased by one element on each iteration."

请问这意味着插入排序不是减少由一个算法？因为它需要比较一下已排序的所有元素，因此服用多于一个迭代的每个元素进行排序。

Would that mean that insertion sort isn't a decrease by one algorithm? As it needs to compare all elements that have already been sorted, therefore taking more then one iteration to sort each element.

还是会的定义指的是事实，即它通过每个元件遍历每一个，逐个分选

Or would the definition refer to the fact that it iterates through each element sorting each one, one by one?

推荐答案

根据这个定义，我想说的是插入排序不降低接一个算法，通过你已经提到的原因。也就是说，你一通的算法后，无法调用插入排序方法对数据的更小的子集，因为你需要的所有数据做插入。

According to that definition, I would say that insertion sort is not decrease-by-one algorithm, by the reason that you have already mentioned. That is, you can't call Insertion Sort method after one pass of the algorithm on smaller subset of the data, as you need all the data to do the insertion.

相信的定义并不是指这样的事实：通过每个元件逐个算法迭代，因为大多数涉及阵列算法能做到这一点，而是使该问题到一个较小的子问题，可在加以解决完全相同的方式，而是用更少的数据。冒泡排序是减少接一个算法，因为在每一个过程中，我们把最大元素的地方，然后我们做冒泡排序上休息 N-1 中的元素完全相同的方式。

I believe the definition does not refer to the fact that "an algorithm iterates through each element one by one", as most algorithms involving arrays will do that, but rather to make the problem into a smaller subproblem which can be solved in exactly the same way, but with less data. Bubble sort is a decrease-by-one algorithm, since in each pass we put the maximum element in place, then we do bubble sort on the rest N-1 elements in the exact same way.

这篇关于通过一种算法降低的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！