谈谈算法设计的复杂度

当你在设计或者在编写一个软件的时候，可能你常常会忽略软件的效率问题。很多人往往在一个项目开始的时候就会将所有的注意力先放在项目的具体实现上，他们往往等关注完项目的实施进展情况后，然后才会去担心软件的执行效率问题。

你也许还很乐观还认为到目前为止你这样做已经很好了，可不幸的事实是真正的效率问题可能正隐藏在你的算法设计中。我想大多数的IT专家肯定都曾学过一些基本的算法，如果你万一稍稍偷了点懒，也没有去温习过这些相关知识的话，那么现在我们将在这里帮助你重新温习下这些内容。

首先你需要考虑是你希望能降低多少复杂度。衡量复杂度有两个主要的方面，一个方面是时间，它指的是要完成一个操作需要多长的时间，另一个方面是空间，它指的是要完成一个操作需要多少的存储空间。

接下来具体谈谈复杂度，对于时间复杂度来说我们是根据每个输入的变量要执行多少步来衡量它的速率，对于空间复杂度来说我们是根据需要多少的存储块来衡量它的效率的，而不是根据绝对的时间或空间来衡量的，因为绝对的时间和空间都是依赖于硬件的。同样的，单步执行的时间长度会被忽略，因为在这时候大量的输入变量是由复杂度类型控制的。

为了更轻松的比较两个算法，我们现在通过使用一些特定的标记来将它们分类。有一些不同的方法可以用来分类，分别是根据最好情况、平均情况和最坏情况来输入一些参数来进行算法比较。我喜欢比较算法的最坏情况，因为一般算法在最坏情况的时候，可能与你感觉的执行会完全不一样的。

为了表述这个，我们使用大写的O来标记，这种方法可以很好的表达一个算法在最坏的情况下，输入一个大小为“n”的变量后，需要执行的步骤。所以，根据下面的例子，你就会明白一个数组简单求和算法的复杂度。

sum(a) {

final_sum = 0

n = length(a)

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

sum += a[i]

}

return final_sum

}

把每一行看作一个单步，我们看到这个算法调用求和n次，执行完整个算法需要n+4步，其中，初始化变量final-sum和变量n各需要一步，设置for循环需要一步，执行return语句需要一步，再就是，执行for循环体需要n步。

现在将问题变化一下，在把数字加到累计总数之前，先将这个数字乘以这个数字在数组中出现的次数。下面的语句将会实现这个功能：

sum_multiple(a) {

final_sum = 0

n = length(a)

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

num = 0

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

if (a[j] == a[i]) {

num++

}

}

final_sum += a[i] * num

}

return final_sum

}

它与先前那个函数类似，除了与先前那个函数有相似的功能之外，它在进行累加求和之前，先数出了数组中每个数字出现的次数。调用这个大小为n的数组的函数，意味着要执行4+n*(1+n*2)步，因为现在外部循环包括2n+1步。