数据结构——算法概述

文章目录

1. 算法定义

2. 批判标准

3. 示例

4.  算法评价标准1：时间复杂度(效率的度量)

执行方法

时间复杂度

代码示例

概念理解

5. 计算时间复杂度

6. 算法评价标准2：空间复杂度(存储量的度量)

空间复杂度定义

O(1) 空间复杂度

O(n) 空间复杂度

---

1. 算法定义

算法是一组有限的、明确的步骤或指令，用于解决特定问题。这些步骤必须是计算机可以执行的操作。通俗地理解，算法就是解决特定问题的方法。

算法的表示形式

• 伪代码：使用接近自然语言的方式描述算法，但更结构化、更接近编程语言。伪代码方便人们理解和交流算法。

• 自然语言：用日常语言描述算法的步骤。尽管自然语言易于理解，但由于缺乏结构和精确性，容易引起歧义。

• 流程图：以图形方式表示算法的流程，通过各种符号和箭头表示操作步骤和流程控制。流程图直观、易于理解。

算法的特性

• 有穷性：算法必须在有限的步骤内完成，并且每一步都在有限时间内完成。递归函数尤其需要注意避免无限递归。

• 确定性：算法中的每一条指令都必须有明确的含义，不能有二义性。确保算法在任何情况下都能按预期执行。

• 可行性：算法描述的操作都可以通过基本运算在有限次数内实现。如果操作不可行，算法就没有实用价值。

• 输入：算法有零个或多个输入，用以描述运算对象的初始状态。输入是算法运行的基础数据。

• 输出：算法有一个或多个输出，反映对输入数据的处理结果。没有输出的算法是无意义的。

2. 批判标准

一个好的算法的设计目标：

• 正确性：

  • 算法应能够正确地解决问题，这是最基本和最重要的标准。正确性包括以下几个层次：
    • 程序没有语法错误。
    • 对于几组测试数据，能得到满足要求的结果。
    • 对于设计的典型和苛刻的测试数据，能得到满足要求的结果。
    • 对于所有合法的输入数据，能得到满足要求的结果。

• 可读性：算法应容易阅读和理解。可读性好的算法有助于交流、维护和修改。

• 健壮性：算法应具有容错能力。当输入非法或错误时，算法应能适当地处理或反应，而不会产生错误结果。

• 通用性：算法应具有广泛的适用性，能够处理一般的数据集合。

• 高效率与低存储量：

  • 效率：指算法执行的时间。算法的效率通常与问题规模有关。
  • 存储量需求：指算法在执行过程中所需的最大存储空间。这也与问题规模有关。

3. 示例

这个例子展示了如何用自然语言、伪代码和流程图三种形式表示一个选择排序算法。每种形式都有其优点和适用场景，选择哪种表示形式取决于具体需求和读者背景。

自然语言描述

选择排序是一种简单的排序算法，它的基本操作是将数组分为已排序和未排序两部分，并从未排序部分选出最小（或最大）的元素，将其放到已排序部分的末尾。具体步骤如下：

1. 从数组的第一个元素开始，设为最小值。
2. 依次与剩余元素比较，如果发现比当前最小值更小的元素，则更新最小值的位置。
3. 扫描完未排序部分后，将最小值与未排序部分的第一个元素交换。
4. 重复上述步骤，将下一小部分的元素排序，直到整个数组排序完成。

伪代码描述

procedure selectionSort(arr: array of integers)
    n = length(arr)
    for i = 0 to n-1 do
        minIndex = i
        for j = i+1 to n-1 do
            if arr[j] < arr[minIndex] then
                minIndex = j
        swap(arr[i], arr[minIndex])
end procedure

流程图描述

flowchart TD
    Start --> A[初始化 n = length(arr)]
    A --> B[for i = 0 to n-1]
    B --> C[初始化 minIndex = i]
    C --> D[for j = i+1 to n-1]
    D --> E{arr[j] < arr[minIndex]?}
    E -->|是| F[更新 minIndex = j]
    E -->|否| G[继续下一个 j]
    F --> G
    G --> D
    D --> H[交换 arr[i] 和 arr[minIndex]]
    H --> B
    B --> End[排序完成]

4.  算法评价标准1：时间复杂度(效率的度量)

执行方法

算法执行时间的度量是评估算法效率的重要指标。常用的方法有两种：

1. 事后统计：

   • 计算机内部进行执行时间和实际占用空间的统计。
   • 问题：必须先运行依算法编写的程序，依赖硬件性能（计算机硬件性能、不同的编程语言），容易掩盖算法本身的优劣；没有实际价值。

2. 事前分析：

   • 求出该算法的一个时间界限函数。
   • 这个时间界限函数与以下因素相关：
     • 依算法选用的各种策略
     • 问题的规模
     • 数据的初始状态
     • 程序设计的语言
     • 编译程序所产生的机器代码的质量
     • 机器执行指令的速度

时间复杂度

时间复杂度是算法评价中非常重要的一个指标，它能有效地帮助我们衡量和比较不同算法的效率。在编写和选择算法时，通过分析其时间复杂度，我们可以选择更高效的算法，从而提高程序的性能。

为了简化问题，抛开硬件和编程语言的影响外，可以认为一个特定算法时间度量 T 的大小，只依赖于问题的规模 n（通常用 n 表示），表示成是问题规模的函数 f(n)。

事前分析中的时间复杂度

时间复杂度表示算法执行所需要的时间随输入数据规模增长的变化。常见的时间复杂度包括：

• 常数时间复杂度： O(1)
• 对数时间复杂度： O(log⁡n)
• 线性时间复杂度： O(n)
• 线性对数时间复杂度： O(nlog⁡n)
• 平方时间复杂度： O(n2)
• 立方时间复杂度： O(n3)
• 指数时间复杂度： O(2n)

代码示例

常数时间复杂度 O(1)

int a = 1;
int b = 2;
int c = a + b;

无论输入规模 nnn 的大小如何，执行时间都是固定的。

线性时间复杂度 O(n)

for (int i = 0; i < n; i++) {
    sum += i;
}

循环体内的操作执行了 n 次，所以时间复杂度是 O(n)。

平方时间复杂度 O(n2)

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        sum += i + j;
    }
}

内外层循环各执行 n 次，总的操作次数为 n×n，所以时间复杂度是 O(n2)。

概念理解

时间复杂度不是执行一段程序的总时间，而是描述某一算法中基本操作的总次数。时间复杂度 T(n) 是用大O符号 O(f(n)) 表示的，其中 f(n) 是问题规模 n 的一个函数。

代码示例

#include <stdio.h>

void playGame(int n)  // n 为问题规模
{
    int i = 1;  // 执行 1 次
    while (i <= n)  // 执行 n + 1 次
    {
        printf("数据已加载%.2lf%%, 即将开始\n", (i + 0.0) / n * 100);  // 执行 n 次
        i++;  // 执行 n 次
    }
    printf("数据加载完毕，开始战斗吧！\n");  // 执行 1 次
}

int main()
{
    playGame(200);
    return 0;
}

将以上各部分的执行次数相加： T(n)=1+(n+1)+n+n+1=3n+3

根据时间复杂度的定义，我们取时间复杂度的最高阶项，并忽略常数系数，所以时间复杂度为： T(n)=O(n)

总结

• 时间复杂度描述的是算法随着输入规模增长，执行时间增长的趋势。
• 在分析时，主要关注循环结构、递归调用等影响执行次数的关键点。
• 最终的时间复杂度表示为 O(f(n))，其中 f(n) 是描述输入规模 n 的函数。
• 时间复杂度为 O(n) 的算法表示其执行时间与输入规模 n 成线性关系。

5. 计算时间复杂度

在计算时间复杂度时，可以使用直接观察法和举例验证等方法，计算出问题规模 n 的函数 f(n)，然后取其增长最快的项。

int m = 5;
int n = 10;
for (int i = 0; i < m; i++)
{
    for (int j = 0; j < n; j++)
    {
        printf("我执行了多少次呢？\n");
    }
}

计算总执行次数

我们可以将外层和内层循环的执行次数相乘，得到总的执行次数： T(m,n)=m×n

• 外层循环执行 m 次。
• 内层循环在每次外层循环执行时，执行 n 次。

因此，整个程序的执行次数为 m×n。

6. 时间复杂度关系

时间复杂度是衡量算法效率的一个重要指标。常见的时间复杂度从低到高依次为：

时间复杂度图展示了不同算法的时间复杂度随输入规模 nnn 增长的变化。横轴表示输入的规模（元素个数），纵轴表示算法执行的基本操作次数。

• O(1)：常数时间复杂度，执行时间不随输入规模变化。
• O(\log n)：对数时间复杂度，执行时间随输入规模对数增长。
• O(n)：线性时间复杂度，执行时间随输入规模线性增长。
• O(n \log n)：线性对数时间复杂度，常见于高效排序算法，如快速排序和归并排序。
• O(n^2)：平方时间复杂度，常见于简单排序算法，如冒泡排序和插入排序。
• O(n^3)：立方时间复杂度，常见于一些嵌套循环算法。
• O(2^n)：指数时间复杂度，常见于解决NP完全问题的算法。
• O(n!)：阶乘时间复杂度，常见于排列问题，如旅行商问题。
• O(n^n)：最差时间复杂度，几乎不可接受。

5.1 常量阶 O(1) 时间复杂度

定义：常量时间复杂度 O(1)O(1)O(1) 表示算法的执行时间与输入数据的大小无关。无论输入数据增加多少倍，栈时/栈空间都不变。这类算法通常不会包含循环或递归操作。

常用算法的实现场景包括：

• 不涉及循环（或有循环，但循环次数与问题规模无关）的算法。
• 原操作执行次数与问题规模无关。

示例：

下面是一个计算从 1 到 n 的和的算法示例，其时间复杂度为 O(1)：

void Sum1(int n)
{
    int sum = 0;                    // 执行 1 次
    sum = (1 + n) * n / 2;          // 执行 1 次
    printf("testSum1:%d\n", sum);   // 执行 1 次
}

运行步骤分析：

• 初始化变量 sum 为 0。
• 计算从 1 到 n 的和，并将结果赋值给 sum。
• 打印 sum 的值。

时间复杂度计算：

• 每条语句都只执行一次，总执行次数是一个常数，与 n 的值无关。
• 因此，该算法的时间复杂度为 O(1)。

5.2 线性阶 O(n) 时间复杂度

定义：线性时间复杂度 O(n)O(n)O(n) 表示算法的执行时间与输入数据的大小成正比。即数据量增大几倍，耗时也增大几倍。

场景：常用算法或场景包括遍历、查找等操作。

示例：

举例1：遍历打印

void Sum2(int n) {
    for (int i = 1; i <= n; i++) { 
        printf("test"); // 执行 n 次
    }
}

该算法的执行时间与输入规模 n 成正比，时间复杂度为 O(n)。

举例2：累加和

void Sum3(int n) {
    int i, sum = 0; // 执行 1 次
    for (i = 1; i <= n; i++) {
        sum += i; // 执行 n 次
    }
    printf("testSum3:%d\n", sum); // 执行 1 次
}

该算法的执行时间与输入规模 n 成正比，时间复杂度为 O(n)。

举例3：数组查找

void Search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            printf("%d", target);
            break;
        }
    }
}

时间复杂度分析：

• 最好情况：目标元素在第一个位置，时间复杂度为 O(1)。
• 最坏情况：目标元素在最后一个位置，时间复杂度为 O(n)。
• 平均情况：假设目标元素在任意一个位置的概率相同，平均时间复杂度为 O(n)。

 

5.3 平方阶 O(n²) 时间复杂度

定义：平方时间复杂度 O(n2)O(n^2)O(n2) 表示算法的执行时间与输入数据的平方成正比。常见于双层遍历和一些简单的排序算法，如冒泡排序和插入排序。

场景：常用算法或场景包括双层遍历、冒泡排序算法、插入排序算法等。

示例说明：双层遍历累加

void Add(int x, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            x = x + 1;
        }
    }
}

时间复杂度分析：两层嵌套循环，每层循环执行 n 次，时间复杂度为 O(n2)O(n^2)O(n2)。

5.4 立方阶 O(n3) 时间复杂度

定义：立方时间复杂度 O(n3)O(n^3)O(n3) 表示算法的执行时间与输入数据的立方成正比。常见于三层嵌套循环的算法中。

示例说明：三层嵌套循环

int test1(int n) {
    int sum = 0; // 执行1次
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                sum++; // 执行n*n*n次
            }
        }
    }
    return sum; // 执行1次
}

int main() {
    int sum = test1(5);
    printf("sum = %d\n", sum); // 125 => 5^3
}

三层嵌套循环，每层循环执行 n 次，总的基本操作执行次数为 n×n×n=n3，时间复杂度为 O(n3)。

5.5 对数阶 O(log⁡2n)时间复杂度

定义：对数时间复杂度 O(log⁡n) 表示算法的执行时间随着输入数据规模的增加呈对数增长。对数时间复杂度通常出现在算法的每一步骤都将问题规模减小一定比例的情况下，例如二分查找。

示例说明：对数时间复杂度的代码

void test1(int n) {
    int i = 1;
    while (i <= n) {
        i *= 2;
    }
}

时间复杂度分析：

• 在每次循环中，i 都会乘以 2，这意味着 i 以指数级别增长。假设循环执行了 m 次，那么最后一次循环时 i=2m。
• 当 i>n 时，循环结束，因此 2m>n，取对数得 m>log⁡2n。
• 所以，这段代码的时间复杂度为 O(log⁡2n)。

5.6 线性对数阶 O(nlog⁡n) 时间复杂度

定义：线性对数阶 O(nlog⁡n) 的时间复杂度表示算法的执行时间随着输入数据规模的增加呈线性对数增长。典型的算法包括快速排序、归并排序和堆排序。它们的特点是在某些步骤上对数据进行分治处理，每次分治处理需要线性时间，但分治的次数为对数级别。

示例：线性对数时间复杂度的代码

void test3(int n)
{
    int x;
    for (int i = 0; i < n; i++) // 外层循环执行 n 次
    {
        x = 1;
        while (x < n / 2) // 内层循环执行 log(n) 次
        {
            x = 2 * x;
        }
    }
}

时间复杂度分析：

• 外层循环执行 n 次，每次外层循环中，内层循环执行 log⁡(n) 次。
• 因此，总的执行次数为 n×log⁡(n)，即时间复杂度为 O(nlog⁡n)。

5.7 平方根阶O(sqrt(n))

平方根阶时间复杂度意味着随着输入数据大小n的增加，算法的执行时间与sqrt(n)成正比。举个例子，当n增大到原来的4倍时，执行时间将增大到原来的2倍。

void fun(int n)
{
    int i = 0, s = 0;
    while (s < n)
    {
        // 基本操作
        i++;
        s = s + i;
    }
}

复杂度为：T(n) = O(sqrt(n))。

在这种情况下，while循环内部的基本操作总共执行了sqrt(n)次。

6. 算法评价标准2：空间复杂度(存储量的度量)

空间复杂度定义

空间复杂度是指算法在运行过程中除了算法本身的指令、常数外，还需要的针对数据操作的辅助存储空间的大小。同样是问题的规模（或大小）n的函数。

记法：S(n)=O(f(n))

常见的空间复杂度主要有：

• 常量空间 O(1)

  • 一个算法如果只需要常量个存储空间来完成算法任务，不随输入规模变化而变化，则空间复杂度为 O(1)。

• 线性空间 O(n)

  • 一个算法如果需要线性个存储空间来完成算法任务，与输入规模呈线性关系，则空间复杂度为 O(n)。

常见的空间复杂度关系

O(1) 空间复杂度

表示算法在执行过程中，所需的辅助存储空间是常量，与输入数据规模无关。即算法的存储空间需求不会随问题规模n的增加而增加。

如果所需空间相对于问题规模n来说是常数，则称此算法为原地工作算法或就地工作算法。

举例：

void test1(int n)
{
    int i = 1;
    while (i <= n)
    {
        i++;
        printf("%d", i);
    }
}

假设一个 int 变量占用 4 个字节，则所需内存空间 = 4（i） + 4（n） = 8 字节。因为在这个例子中，所需的内存空间与输入的大小 n 无关，所以空间复杂度为 O(1)。

内存布局

• 程序代码：程序代码部分占用固定内存。
• 数据：包括局部变量 i 和参数 n。
• 其他内存：系统和其他程序占用的内存。

O(n) 空间复杂度

表示算法在执行过程中，所需的辅助存储空间与输入数据规模成线性关系。即算法的存储空间需求会随问题规模n的增加而增加。

如果所需空间相对于问题规模n来说是线性的，则称此算法的空间复杂度为O(n)。

举例：

void test2(int n)
{
    int i;
    int arr[n];
}

总的内存空间为 4（i） + 4n（arr 数组） + 4（n）= 4n + 8 字节。

由于所需的内存空间与输入的大小 n 成线性关系，因此空间复杂度为 O(n)。

内存布局

• 程序代码：程序代码部分占用固定内存。
• 数据：包括局部变量 i、参数 n 和数组 arr。
• 其他内存：系统和其他程序占用的内存。

递归算法有时会体现出线性时间复杂度。比如下面这个递归函数，它的时间复杂度是 O(n)。

void recursion(int n) {
    if (n == 1) {
        printf("递归函数\n");
    } else if (n > 1) {
        recursion(n - 1);
    }
}

int main() {
    recursion(5);
}

时间复杂度分析:

• 对于每一次函数调用，都会检查 n 的值，进行一次递减直到 n 为 1。
• 因此，总共会进行 n 次递归调用。
• 时间复杂度为 O(n)。

内存分析

当 recursion(5) 被调用时，递归调用栈会依次压入 recursion(4)，recursion(3)，recursion(2) 和 recursion(1)。如图所示，每个函数调用占据了栈空间。