谈谈算法设计的复杂度

现在，我们已经在每个算法中都采取了临时步数的观点，也就是说，在这里我们认为每一行是一步，当像“sum += a[j] * numbers[a[j]]”这样的语句，虽然这条语句包括乘法查找并且能够被编译成10条单独的硬件级指令，但是我们还只将它认为是一条语句。

虽然这点不是特别重要，但是当你回想它的时候，即使在我们假设的第二个例子中，我们进行计数的每一步确实需要执行10条指令，然而只要第一个程序没有改变的话，第一个程序执行的时间仍然还是第二个程序的60，000多倍。

我们真正感兴趣的是算法的排序，为了方便起见，我们把复杂度统一的归纳为最大部分的大小。例如，sum_multipes这个函数我们说它的时间复杂度是O（n2），而sum_multipes2这个函数的时间复杂度是O（n）。我们已经知道了，对于足够大的n来说，不管具体如何实现的，O（n）复杂度的算法一直比O（n2）复杂度的算法要好。

这个方法对于时间复杂度来说是非常好的方法，然而对于空间复杂度来说呢？你可能注意到了，sum_multipes2这个算法是通过增加空间来达到节省执行时间的目的的，也就是增加了可变的numbers这个数组。

现在，在这个方案中它可能是一个好的转换，因为我们只用了n个存储块就降低了n倍的时间复杂度。如果你的程序是运行在存储资源非常珍贵的环境下，那么你就应该小心的去做这个改变。一般来说，你可以通过使用更多的存储空间或者是通过高速缓冲存储器来存储经常调用的函数这两种方法来改进算法的时间复杂度。这个算法的理论是基于动态程序设计的。

让我们将这些思想应用到一个事先策划好的例子中去：这个方案中描述的是非常经典的排序算法，因为它们使用得相当广泛，所以一直都备受关注。我们在这里挑选了两个普通的排序算法来进行比较：选择排序和快速排序。

即使你开发的平台已经将排序算法作为语言的一部分给了你，或者是作为一个API给了你，但是一个定制的排序算法仍然能明显的提高速度，所以它是值得我们去阅读研究的。

选择排序可能是所有排序算法中最容易掌握的一个了，它与大部分人直觉性的排序类似，也就是说，这种方法与人们玩扑克牌排序游戏时使用的方法非常类似。它有两个主要的步骤：首先，从数组中找出最小值，然后把这个最小值与数组的第一个元素进行交换。在这里我们不关心数组开始的时候就已经有序的元素，而是直接对整个数组重复执行这个操作，这样继续下去你就可以最终得到一个有序的数组了。这种选择排序算法的实现如下所示：

selection_sort(a) {

n = length(a)

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

min = i

for (j = i + 1; j < n; j++) {

if (a[j] < a[min]) {

min = j

}

}

temp = a[i]

a[i] = a[min]

a[min] = temp

}

}

根据这个嵌套循环，你很容易就能得到这个算法的时间复杂度是O（n2）。从效率上来看，这是一个相当糟糕的排序算法，因此在实际应用中，它几乎从来没有被使用过，就像那个声名狼藉的冒泡排序一样。

另外一方面，快速排序在现实世界中应用的相当广泛，因为它有更快速的平均查询速度，同时只需要很少的额外存储空间。快速排序也遵循相对简单的步骤序列：首先，在数组中选择一个元素，把它称作中轴，然后，把数组重新排序，使数组中所有比中轴小的数都放在它的前面，所有比中轴大的数都放在它的后面。这样，就得到了两个新数组，对新得到的两个数组再使用快速排序算法，这样一直到每个数组中只包含零个或一个元素为止，使用这种方法排好序的数组就是一个从小到大的有序数组了。下面给出的这个例子来自Wikipedia快速排序入门：

partition(array, left, right, pivotIndex) {

pivotValue = array[pivotIndex]

swap(array[pivotIndex], array[right]) // Move pivot to end

storeIndex := left

for (i = left; i < right; i++) {

if (array[i] < pivotValue) {

swap(array[storeIndex], array[i])

storeIndex := storeIndex + 1

}

}

swap(array[right], array[storeIndex]) // Move pivot to its final place

return storeIndex

}

quicksort(array, left, right) {

if (right > left) {

select a pivot index (e.g. pivotIndex = left)

pivotNewIndex := partition(array, left, right, pivotIndex)

quicksort(array, left, pivotNewIndex-1)

quicksort(array, pivotNewIndex+1, right)

}

}

最坏情况下的快速排序算法的时间复杂度是O（n2），这种情况就跟选择排序的时间复杂度是一样的，它是出现在，当你选择的中轴是这个数组中的最小值或者是数组中的最大值的时候。然而，快速排序的平均时间复杂度是O（nlog2n），这种方法的时间复杂度相对于先前的算法就有明显的改善。

如果我们要对一个有上百万条记录的数组进行排序，两种不同方法的时间复杂度比是一万亿比一千九百万的关系——相当于相差50，000倍。事实上，可以证明的最好的一般比较排序算法的平均时间复杂度是nlogn。在这里证明过程我就省略了，但是它可以说明快速排序算法相当接近于这个最好的比较排序算法。