[自学使用]算法设计与分析L1（一）

Syllabus:

    model of computation->algorithm design & analysis techniques->computation complexity

学有余力、查一些算法：https://walkccc.me/CLRS/

Algorithm:

    model of computation

    algorithm design

    algorithm analysis

Model of computation:

    machine- and language- independent algorithms,running on an abstract machine

    turing machine

    RAM model: simple but powerful

Algorithm design:

    composition of simple operations, to solve analgorithm problem

Algorithm analysis:

    amount of work done/ memory used (on the worst/average case)

    advanced issues (optimality, approximation ratio...)

两个算法例子：

    1.两个非负整数（non-negative integers）m和n最大公约数GCD（greatest common divisor）

    2.在数组E[1..n]中找到关键字K

正确性：（一个一个试，试不完）对于任何合法输入（包括corner case），输出总是正确的

证明正确性？数学归纳法（mathematical induction）

    weak / strong principle

算法分析：标准：例子：