Chapter 3 - Algorithms

1 Algorithms

An algorithm is a finite set of precise instructions for performing a computation or for solving a problem.

Example: Can we develop a procedure that takes as input a computer program along with its input and determines whether the program will eventually halt with that input.
Does there exist a procedure H(P,I), which takes as input a program P and the input I to P.
H outputs “halt” if it is the case that P will stop when run with input I.
Otherwise, H outputs “loops forever.”

即，是否有一个通用的判定程序来判断一个程序是否会停下来？
假设存在这么一个判定程序H
我们构造这样一个程序D

def D(P):
    # 调用H，判断"程序P在输入为P自身时是否会停机"
    if H(P, P) == "halt":
        # 如果H说P(P)会停机，那么D就故意进入无限循环
        while True:
            pass  # 永远执行空操作，不会停机
    else:
        # 如果H说P(P)永远循环，那么D就立刻停机
        return  # 程序结束，停机

运行D(D)，如果H(D,D)说halt，那么D(D)应该会停下来，但这时D(D)将一直循环下去。
假设 H (D,D) 输出 “loops forever”
这意味着 H 判定：程序 D 在输入为 D 时永远不会停机。但根据 D 的定义，当 H (P,P) 输出 “loops forever” 时，D 会立刻停机。因此：D(D) 会停机
无论 H 给出什么答案，都会和 D (D) 的实际行为矛盾。这说明我们最初的假设 ——“存在一个完美的通用停机判定程序 H”—— 是错误的。

2 The Growth of Functions

基础知识点见数据结构的笔记
证明
上界证明是容易的，左边拆成加法就行了
我们将求和式拆分为前半部分和后半部分，只对后半部分进行下界估计：

对于后半部分的每一项 ，有：

后半部分共有 项，因此：

当 时，，代入得：

取 ，，满足 的定义。

Put the functions below in order so that each function is big-O of the next function on the list.










注意顺序，比如我这么列 logn，2n,logn=O(2n)就是对的
A is big-O of B means A has lower complexity than B
f(x) is O(g(x)) is read as “f(x) is big-O of g(x)”
9 5 3 6 2=8 1 4 7 10

3 Complexity of Algorithms

There are two important aspects of the computational complexity of an algorithm:
Space Complexity: gives the approximate amount of memory required to solve a problem of size n.

• Often tied in with the particular data structures used to implement the algorithm

Time Complexity: gives the approximate number of operations required to solve a problem of size n.