函数及其增长

衡量算法性能的标准是用函数来表示的。对于不熟悉数学的读者，下面我们对函数进行解释。

函数

可以把函数想象成一台机器或一个黑箱，从一端输入数据，从另一端输出结果。

我们来看下面这个函数：

$f ( n ) = n^2$

这是表达函数的传统形式，其中n是输入到“机器”中的参数。输出结果以输入的形式表示；在上述函数中，输出是n²，即根据输入n计算得出。输入变量n可以取不同的值，输出也会随之变化。下表展示了当n取不同整数值时，函数生成的输出值。

函数的比较

现在你已经了解了什么是函数。接下来看看如何比较两个函数。考虑以下两个函数：

$f ( n ) = n^2$ $f ( n ) = n^3$

如果我们限制n只能取非负数值，那么就可以判断哪一个函数产生的输出数值更大。输出更大的函数被认为增长得更快。

从输出可以看出，当 n > 1 时，函数 f ( n ) = n³ 的增长速度比 f ( n ) = n² 更快。

重新审视插入排序的分析

在上一节中，我们推导出了对大小为n的输入数组进行排序时所执行的总指令数的代数表达式。该表达式可表示为关于n的函数如下：

$f ( n ) = [ 2 * (n + 1) + 2n ] + [ 2n + 7 [ \frac{n(n-1)}{2} ] ]$

我们已将插入排序的时间复杂度表示为输入规模的函数。在接下来的章节中，我们将运用数学工具进一步深入分析。

函数之间的比较可能会让你联想到课程开始时提到的赛道竞赛示例。我们的目标正是如此：将算法的性能建模为函数，其中输入n代表算法的输入规模。我们并不直接关心函数输出的具体数值，而是关注它们的增长趋势——而这种增长特性正取决于函数所产生的数值变化。