Algorithms and Functions(算法和函数)

Functions in General(普遍的函数)

Definition 4.1. Formally, a function consists of three parts:
• A collection A of possible inputs. We call this the domain of our
function.
• A collection B describing the type of outputs that our function
will generate. We call this the codomain of our function.
• A rule f that takes in inputs from A and generates outputs in B.
Furthermore, in order for this all to be a function, we need it to satisfy
the following property:

For every potential input a from A, there should be exactly one b in
B such that f(a) = b.

In other words, we never have a value a in A for which f(a) is undefined,
as that would cause our programs to crash! As well, we also do not allow
for a value a ∈ A to generate “multiple” outputs; i.e. we want to be able
to rely on f(a) not changing on us without warning, if we keep a the
same.

一般来说函数由三个部分组成：

可能输入的集合A。我们称它为函数的定义域。
描述函数将生成的输出的集合B。我们称这个为函数的上域(注意此处不是值域)。
从A中获取输入并在B中产生输出的规则f。

此外，为了使它成为一个函数，我们需要它满足以下性质：
对于A中的每一个可能的输入a，B种应该有一个b使f(a) = b。

换句话说，在a中没有一个值a是f(a)未定义的，因为这将导致我们的程序崩溃!同样，我们也不允许值a∈a产生“多个”输出;也就是说，我们希望f(a)不会毫无预兆地改变，如果我们保持a不变的话。

什么是上域？
值域是上域的一个子集，上域是可能输出的集合，值域是实际输出的集合！
一个函数必须给每一个有效的输入指定唯一的结果。

假设你有一团揉好的白面，准备做彩色馒头，你加入紫薯能做出紫色馒头，加入火龙果能做出粉红色馒头，加入巧克力，加入艾草，加入…
令f(x)=“白面加入食材x做出的馒头颜色”，其上域就是所有颜色的集合，而值域是函数转变定义域后的对象的集合。
———-值域是上域的一个子集，上域是可能输出的集合，值域是实际输出的集合！

这里解释了值域的定义：
我们将f的值域定义为上域中函数在定义域中实际发送值的所有值的集合。

定义了函数的符合，这里除了要掌握符号表达形式，还有内部函数的值域一定要是外部函数定义域的子集！

Algorithms(算法)

Definition 4.3. An algorithm is a precise and unambiguous set of
instructions.

算法是一组精确而明确的指令。

如图是两种算法：

a%n的算法
判断素数的算法

还有经典的排序算法(10种)，可以自行了解

Comparing Runtimes: Limits

涉及到了极限的概念

如果满足上式，那么我们就可以说函数f(n)增长的速度快于g(n)

Limit Techniques and Heuristics

Observation 4.12. Plugging In Values. Probably the simplest thing
you can do, when given a limit, is just physically plug in numbers and
figure out where the function is going.

代入值。可能你能做的最简单的事情，当给出一个极限时，就是物理地代入数然后算出函数的走向。

这里提供了一个建议，简化分数对求极限的重要性