文章目錄
- Algorithms and Functions(算法和函數)
- Functions in General(普遍的函數)
- Algorithms(算法)
- Comparing Runtimes: Limits
- Limit Techniques and Heuristics
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. 代入值。可能你能做的最簡單的事情，當給出一個極限時，就是實體地代入數然後算出函數的走向。
這裡提供了一個建議，簡化分數對求極限的重要性