|
《Windows游戏编程大师技巧》（第二版）第11章(7) 对吗？错了！如果要计算循环时间，你应当将循环自身花费的时间包括进去。这些时间包括变量的初始化、比较、增量和循环的跳转。将这些时间加进去，如下式所示：
Cyclesinitialization+(50+Cyclesinc+Cyclescomp+Cyclesjump)*n
上式是一个较好的估计。这里，Cyclesinc、Cyclescomp和Cyclesjump分别代表增量、比较和跳转所需的周数。在奔腾级的处理器上，其值约为1~2周。因此，在这种情况下，循环本身所花费的时间和程序内部工作循环所需用的时间一样多。这一点是非常重要的。
比如，许多游戏程序员在处理有关像素绘图的问题时，将其编写成函数而非一个宏或内联代码。因为像素绘图函数是如此简单，以至于调用这个函数比直接画图所需时间还要多！所以在设计循环时必须确保循环内部有足够的工作，而且循环运行所需时间要远大于循环自身所花费的时间。 现在让我们来看一看另一个例子——它的时间复杂度高于n：
// outer loop
for (i=0; i<n; i++)
{
// inner loop
for (j=1; j<2*n; j++)
{
// do work
} // end for j
} // end for i
在这个例子中，我们假定循环中工作部分执行所需时间远大于实现循环机制所花费的时间，这样我们就不考虑循环自身花费时间而只考虑循环执行的次数。这个程序的外部循环次数为n次，内部循环的次数为2n-1次，所以内部代码总的执行次数为：
n*(2*n-1) = 2*n2-n
上式由两项构成。2n2是主项，其值要远大于后一项，并且随n取值的增加，两项的差值也增大。如图11-5所示。
.
图11-5：2n2-n的增长速率
当n较小比如n=2时，上式的值为：
2*(2)2 - 2 = 6
在该情况下，n这项减去总花费时间的25%。但当n的值增大时，比如n=1000：
2*(1000)2 - 1000 = 1999000
这时，n这项只减去总花费时间的0.5%，可以忽略不计。现在读者该明白了为什么2*n2项是主项或更简单地说n2是主项。所以，这时的算法复杂度是O(n2)，这是非常糟糕的，以n2运算的算法是不能令人满意的，因此当你提出这样一个算法时，你最好从头再来！
上述都是为渐近分析作准备的。最低要求是：你必须能够粗略地估计你的游戏程序中循环的执行时间。这将有助于你挑选算法和所需编码空间。 递归
我们下一个所要探讨的主题是递归（Recursion）。递归是一种应用归纳的方法求解问题的技术。递归的基本含义是把许多问题连续分解成同一形式的简单问题，直到能够真正的求解为止。然后将这些小问题进行归纳、组合进而使整个问题得到解决。听起来是不是很美妙？ 在计算机编程中。我们通常使用递归算法来实现搜索、排序和一些数学计算。递归的前提非常简单：编写一个函数，该函数具有调用自己来求解问题的能力。是不是听起来不可思议？其关键在于该函数调用自己时，就在堆栈里创建一组新的局部变量，所以相当于一个新的函数被调用。你惟一需要注意的是函数不能溢出堆栈，并且要有终止条件，程序结束时还要有结束处理代码以保证堆栈通过return()释放空间。让我们看一个标准的实例：阶乘的计算。一个数的阶乘写作n!，其含义如下：
n! = n*(n-1)*(n-2)*(n-3)*...(2)*(1)
并有0! = 1! = 1
Thus, 5! is 5*4*3*2*1.
这样，5!就是5*4*3*2*1。
以下是用通常的方法编写的计算代码：
// assume integers
int Factorial(int n)
{
int sum = 1; // hold result // accumulate product
while(n >= 1)
{
sum*=n; // decrement n
| 
