1. 什么是算法

算法的非形式描述：算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。(Knuth给出的概念)

  算法是解决一确定类问题的任意一种特殊的方法，可以分为数值计算方法和非数值计算方法。数值计算方法用于解决数值问题，如插值计算、数值积分等；非数值计算方法则主要用于解决非数值问题，进行判断和比较。

2. 算法的五个重要特性

  算法作为解决问题的特殊方法，在其设计和实现过程中必须满足一系列重要特性，以保证其正确性和有效性。算法必须满足下面五个重要特性：

a. 确定性（Definiteness）

  确定性是指算法中的每一种运算都必须有确切的定义，不存在二义性。换句话说，对于给定的输入，算法必须按照一定的规则进行计算，得到确定的输出，而不会因为不同的解释或情况而导致结果的不确定性。

  • 举例： 考虑一个简单的排序算法，如冒泡排序。冒泡排序的每一步操作都是确定的，即比较相邻元素并交换顺序，直到数组完全有序为止。无论初始数组如何，冒泡排序都会按照同样的规则进行排序，得到确定的结果。
  • 反例:
    • 5/0；
    • 6或7与x相加。

b. 能行性（Effectiveness）

  能行性要求算法中的每一步运算都是基本运算，理论上能够用纸和笔在有限时间内完成。换言之，算法中的操作必须是可行的，不涉及超出计算能力的复杂运算或无法实现的操作。

c. 输入（Input）

  算法可能有零个或多个输入，这些输入来自于特定的对象集合。输入是算法运行的起点，通过对输入的处理，算法得以产生输出。

d. 输出（Output）

  算法产生一个或多个输出，这些输出与输入之间存在特定的关系。输出是算法最终的结果，它是对输入经过处理得到的信息。

e. 有穷性（Finiteness）

  有穷性要求算法在执行有限步运算后终止。换句话说，算法不能进入无限循环或无限递归的状态，必须在有限时间内产生输出。

以Euclidean算法为例

  Euclid算法是求两个正整数的最大公约数的著名算法：

  • 算法原理

    • 该算法基于如下原理：对任意两个正整数m和n(m≥n)，它们的最大公约数等于n和m模n的余数r的最大公约数。即gcd(m，n) = gcd(n，r)。
    • 算法反复应用这个原理，让n和r更新为更小的两个数，直到r变为0为止。当r=0时，n就是m和n的最大公约数。

  • 算法分析

    • 时间复杂度为O(log(min(m，n)))，对于数据规模较小的情况，运行速度很快。
    • 空间复杂度为O(1)，只需要常量级的辅助空间。
Procedure Euclid (m, n)
    // 求正整数m和n (m≥n)的最大公因数
    r ← Mod(m, n)
    While r≠0 Do
        m ←n. n ←r. r ←mod(m, n).
    Repeat
    Return n
End Euclid
  1. 确定性 (Definiteness)
    • 算法的每一个步骤都是明确无歧义的。给定输入m和n，算法中每个操作的结果都是确定的，不存在任何模糊性。
  2. 可行性 (Effectiveness)
    • Euclid算法中的每一个步骤，包括求余数、判断条件等，对于可计算的函数来说都是可行的基本操作，因此整个算法是可以用计算机来实现的。
  3. 输入 (Input)
    • Euclid算法的输入是两个正整数m和n，要求m>=n。
  4. 输出 (Output)
    • Euclid算法的输出是m和n的最大公约数。一旦算法终止，输出结果就是确定的。
  5. 有限性、有穷性 (Finiteness)
    • Euclid算法在有限的步骤后一定会终止。因为在每一次迭代中，余数r都会比前一步的n小。由于正整数是有限的，因此最终余数r会变为0，算法终止。
#include <iostream>
using namespace std;

int Euclid(int m, int n) {
    // 求正整数m和n (m≥n)的最大公因数
    int r = m % n;
    while (r != 0) {
        m = n;
        n = r;
        r = m % n;
    }
    return n;
}

int main() {
    int m, n;
    cout << "Enter two positive integers (m >= n): ";
    cin >> m >> n;

    // 确保m >= n
    if (m < n) {
        swap(m, n);
    }

    int gcd = Euclid(m, n);
    cout << "The GCD of " << m << " and " << n << " is: " << gcd << endl;

    return 0;
}

3. 计算过程与算法的区别

  计算过程不一定满足算法的有穷性。例如，操作系统在没有任务时不会终止，而是进入等待状态，这种情况不符合算法的定义。

4. 算法学习的基本内容

  算法学习的基本内容包括如何设计、表示、确认、分析和测试算法。设计算法需要应用基本的设计策略，确保算法在实践中有效。

程序 = 算法 + 数据结构 (By Niklaus Wirth )

a. 如何设计算法

  在面对具体问题时，设计算法需要运用一些基本的设计策略，规划出解决问题的方法。这些策略被实践证明是有用的，广泛应用于计算机科学、运筹学、电子工程等领域，从而设计出精致有效的好算法。掌握这些策略可以帮助设计更多好的算法。

b. 如何表示算法

  设计的算法需要以恰当的方式进行表示。一种常用的方式是采用结构程序设计的方法，即将算法表示为一系列结构化的步骤，以便于理解和实现。此外，也可以使用SPARKS（Structured Programming Algorithm Realization Kernel System）程序设计语言，这种语言简单明了，能够清晰地表达算法的思想和逻辑。

c. 如何确认算法

  算法确认是指证明该算法对所有可能的合法输入都能给出正确答案的过程。确认算法的目的是确保该算法能够正确无误地工作。确认算法可以采用多种方法，包括穷举法、推理（如数学归纳法、反证法）、构造性证明和测试。通过这些方法，可以确定算法在各种情况下都能正确运行。

d. 如何分析算法

  分析算法时，需要考察算法执行时占用的CPU时间和存储空间。这种分析可以定量地评估算法的性能，帮助选择最合适的算法解决问题。常用的分析方法包括时空分布图和对算法的具体执行情况进行测试，以验证分析的正确性。

e. 如何测试程序

  测试程序是确认算法正确性的重要步骤。调试是常用的测试方法之一，通过调试可以发现程序中的错误，但不能保证程序没有错误。测试程序时，需要使用各种给定数据执行程序，并测定计算时间和空间，以印证之前的分析是否正确。通过测试程序，可以找出实现最优化的有效逻辑位置，并进一步改进算法的设计和实现。