谈谈算法设计的复杂度

整个方法在调用这个函数时需要2n2+n+4步。如果这个数组有10个元素，那么它需要214步，然而，对于一个有100个元素的数组，它则需要20，000多步才能完成。这是一个非常大的增量。不过当我们用另外一个方法来实现这个功能的时候，这个增量将会改变：

sum_multiple2(a) {

final_sum = 0

n = length(a)

numbers = dict()

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

if (numbers.has(a[i])) {

numbers[a[i]]++

} else {

numbers[a[i]] = 1

}

}

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

final_sum += a[j] * numbers[a[j]]

}

return final_sum

}

在这个例子中，我们预计算了数组中每个值出现的次数。为了实现这个目的，我们使用了一个新的数据类型来存储这些值。它的实现并不是很重要，只要我们能够确定我们能在常数时间内将值插入和取出就可以了。

在支持它们的语言中，它们被作为散列或者字典的标准，或者如果你不太幸运（也就说你使用C语言）的话，你可以认为它是一个max（a）大小的整型数组。如果这个类型包含a这个给定的值的话，那么这个方法就将简单的返回一个真值。

总之，使用这个方法，在我们取出这个数的时候，你就能看到它是如何计算出每个值出现的次数的，这样在一开始我们就可以进行累加并存储它出现的次数。让我们来看看这个帮助——sum_multiple2需要执行3n+6步：通常的初始化需要执行三步，再加上将每一个数字出现的次数输入到字典中需要两步，最后还有一步就是进行累加求和。

如果一个数组有10个元素，那么它需要执行36步才能完成，如果有100个元素，那么完成它需要306步。这种方法在处理100个元素的数组时，比第二个版本要快65倍。如果说，我们有一个一百万个元素的数组时，使用第一个版本需要执行2万亿步之多，而使用第二种方法只要执行300万步，两者相差650，000倍之多。