谈谈算法设计的复杂度

接下来，我将向大家介绍第二种改善算法的主要方法：那就是根据你要进行排序的数据来构造一个算法，从而避免标准算法中可能降低性能的部分。现在我将告诉你这是什么意思：如果你有一个无序的数组，其中包括从1到n中所有的元素，并且这些元素不重复出现。

对这个数组进行排序的话有一个算法只需要O（n）的时间复杂度。稍等一下，在上一段中我不是说最好的排序算法的时间复杂度是nlogn吗？对，上一段中所说的仅仅是一般情况，在那种情况下你必须对元素的大小进行比较后才能排序。这里是如果你能把比较这部分去除掉，那么你的算法将会运行的更快。下面让我们来看一下这段桶排序算法：

bucket_sort(a) {

n = length(a)

sorted = array of size n

for (i = 0; i < n; i++) {

sorted[a[i]] = a[i]

}

return sorted

}

在这个算法中，利用每一个元素的值作为排序数组的下标，这样我们对数组搜索一次就能完成整个数组的排序了。这是一个简单的整数排序例子，但是如果你有1，000个记录，而这些记录中有从0到1000个连续的ID号的话，使用这种排序方法将使你的算法效率得到明显的提高。当然假如你不能使用值来作为索引的话，这种方法就不能很好的发挥它的作用，所以这种排序方法只适合对整数进行排序。

既然现在你已经浏览了这些基本算法，那么这时请再注意一下你的代码——你是否确定这些代码能达到你所希望的效率？假如你愿意把时间花费在改善你的代码上的话，也希望你的代码能像这里的某一个代码一样，试着也这样去做对你来说将是非常值得的；把一块代码分成一个更小的类，对于提高效率会有非常好的效果。

下次，在你直接跳入下一个项目议题之前，请你试试花一点点时间去想想前进的最好方式是什么！——这样你会非常感谢你自己在为后面的代码而花了那么一点点时间。

责任编辑:德东

查看本文国际来源