零基础数据结构与算法——第一章：基础下

算法复杂度分析的基础知识，包括大O表示法和常见的时间复杂度。这些工具帮助我们评估和比较不同算法的效率。最后，我们介绍了编程语言中的基本数据类型和复合数据类型，它们是构建数据结构的基础。

qqxhb

968人浏览 · 2025-06-23 09:14:32

qqxhb · 2025-06-23 09:14:32 发布

1.5 复杂度分析入门

什么是算法复杂度

想象你正在比较不同的路线去上学：走路、骑自行车、坐公交车。你会关心什么？可能是时间（需要多久）和成本（需要多少钱）。算法复杂度就是类似的概念，它帮助我们评估算法的效率。

算法复杂度是衡量算法执行效率的指标，主要包括：

时间复杂度：算法执行所需的时间随输入规模增长的变化趋势
空间复杂度：算法执行所需的额外空间随输入规模增长的变化趋势

生活中的例子：

时间复杂度就像是估计做一道菜需要多长时间，随着食材量的增加，烹饪时间如何变化
空间复杂度就像是估计做这道菜需要多大的厨房空间，随着食材量的增加，所需空间如何变化

大O表示法

大O表示法是描述算法复杂度的数学符号，表示算法执行时间（或空间）与输入规模之间的关系。它关注的是算法性能的增长趋势，而不是具体的执行时间。

为什么使用大O表示法？因为具体的执行时间会受到硬件、编程语言等因素的影响，而增长趋势是算法本身的特性。

生活中的例子：

如果你说"我洗一件衣服需要5分钟，洗10件衣服需要50分钟"，这就是一个线性关系，可以用O(n)表示
如果你说"我做一个三明治需要3分钟，做10个三明治也只需要3分钟（因为可以同时做）"，这就是一个常数关系，可以用O(1)表示

常见的时间复杂度

O(1)：常数时间复杂度

无论输入数据有多少，算法的执行时间都是固定的。

例子：

数组的索引访问：array[5]无论数组有多大，访问特定位置的元素所需时间都是相同的
哈希表的查找：理想情况下，哈希表的查找操作是O(1)的

生活中的例子：

无论书架上有多少本书，如果你知道具体位置，拿一本特定的书所需时间基本相同

// O(1)示例
public int getFirst(int[] array) {
    return array[0];  // 无论数组多大，这个操作都是常数时间
}

O(log n)：对数时间复杂度

随着输入规模的增加，执行时间以对数方式增长。这是非常高效的算法。

例子：

二分查找：每次比较后，搜索范围减半
平衡二叉搜索树的查找操作

生活中的例子：

查字典：你不会从第一页开始一页页查找，而是会根据字母顺序，每次打开字典，缩小一半的查找范围

// O(log n)示例 - 二分查找
public int binarySearch(int[] sortedArray, int target) {
    int left = 0;
    int right = sortedArray.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (sortedArray[mid] == target) {
            return mid;
        } else if (sortedArray[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;  // 没找到
}

O(n)：线性时间复杂度

执行时间与输入规模成正比。

例子：

遍历数组或链表
线性搜索

生活中的例子：

检查一叠卡片中是否有特定的卡片，你需要一张张检查，卡片数量翻倍，时间也翻倍

// O(n)示例 - 线性搜索
public int linearSearch(int[] array, int target) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == target) {
            return i;
        }
    }
    return -1;  // 没找到
}

O(n log n)：线性对数时间复杂度

比线性时间复杂度略差，但仍然是高效的算法。

例子：

高效的排序算法，如归并排序、快速排序（平均情况）

生活中的例子：

给一副扑克牌排序：你可能会先粗略分组（分成几堆），然后再细致排序每一堆，最后合并

// O(n log n)示例 - 归并排序（简化版）
public void mergeSort(int[] array) {
    if (array.length <= 1) return;
    
    // 分割数组
    int mid = array.length / 2;
    int[] left = Arrays.copyOfRange(array, 0, mid);
    int[] right = Arrays.copyOfRange(array, mid, array.length);
    
    // 递归排序
    mergeSort(left);
    mergeSort(right);
    
    // 合并结果
    merge(array, left, right);
}

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

执行时间与输入规模的平方成正比。这类算法在输入规模较大时效率较低。

例子：

简单的排序算法，如冒泡排序、插入排序
嵌套循环遍历

生活中的例子：

比较班级中每两个学生的身高：如果有n个学生，你需要进行n×(n-1)/2次比较

// O(n²)示例 - 冒泡排序
public void bubbleSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                // 交换元素
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

O(2^n)：指数时间复杂度

执行时间随输入规模呈指数增长。这类算法通常只适用于小规模输入。

例子：

递归计算斐波那契数列（未优化版本）
穷举所有子集

生活中的例子：

尝试破解一个密码：如果密码长度是n，且每位有10种可能（0-9），则可能的组合有10^n种

// O(2^n)示例 - 未优化的斐波那契数列计算
public int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

如何分析算法复杂度

分析算法复杂度是一项重要技能，可以通过以下步骤进行：

1. 识别基本操作

确定算法中的基本操作，即执行次数与输入规模相关的操作。通常是：

赋值操作
算术运算
比较操作
数组索引访问
函数调用等

2. 确定操作执行次数与输入规模的关系

分析基本操作的执行次数如何随输入规模n的变化而变化。

例如，对于简单的循环：

for (int i = 0; i < n; i++) {
    // 某操作
}

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

对于嵌套循环：

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // 某操作
    }
}

内部操作执行了n×n = n²次，所以时间复杂度是O(n²)。

3. 使用大O表示法表示最终结果

在确定了操作次数与输入规模的关系后，使用大O表示法表示最终结果。记住以下规则：

只保留增长最快的项：如果时间复杂度是3n² + 2n + 1，简化为O(n²)
忽略常数系数：如果时间复杂度是5n，简化为O(n)
关注最坏情况：通常我们分析的是算法在最坏情况下的性能

实例分析

让我们分析一个简单的算法：

public boolean containsDuplicate(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] == nums[j]) {
                return true;
            }
        }
    }
    return false;
}

分析：

基本操作是比较nums[i] == nums[j]
外层循环执行n次，内层循环平均执行(n-1)/2次
总操作次数约为n×(n-1)/2，即O(n²)

因此，这个算法的时间复杂度是O(n²)。

复杂度分析的重要性

为什么要学习复杂度分析？

选择合适的算法：了解不同算法的复杂度，可以根据实际需求选择最合适的算法
预测性能瓶颈：通过复杂度分析，可以预测算法在大规模数据下的性能表现
优化代码：了解复杂度后，可以有针对性地优化代码，提高效率

记住，在实际应用中，常数因子和低阶项也可能影响实际性能，尤其是在输入规模较小时。但对于大规模输入，渐近复杂度（大O表示法）是最重要的考量因素。

1.6 编程语言中的数据类型

在学习数据结构之前，我们需要了解编程语言中的基本数据类型，它们是构建复杂数据结构的基础，就像砖块是建造房屋的基础一样。

基本数据类型

基本数据类型是编程语言内置的、不可再分的数据类型，就像元素周期表中的原子一样。

整数类型

整数类型用于表示没有小数部分的数值。

在不同的编程语言中，整数类型可能有不同的大小和范围：

Java：byte(8位)、short(16位)、int(32位)、long(64位)
Python：int（可以表示任意大小的整数）
C/C++：char(8位)、short(16位)、int(通常32位)、long(至少32位)、long long(至少64位)

生活中的例子：

整数类型就像是计数器，只能显示整数，不能显示小数
不同大小的整数类型就像不同大小的停车场，能容纳的车辆数量不同

// Java中的整数类型示例
byte smallNumber = 127;        // -128到127
short mediumNumber = 32767;    // -32768到32767
int regularNumber = 2000000000; // 约-21亿到21亿
long bigNumber = 9000000000000000000L; // 非常大的范围

浮点类型

浮点类型用于表示带小数部分的数值。

常见的浮点类型：

Java/C/C++：float(32位)、double(64位)
Python：float（通常是64位）

浮点数的精度有限，可能会有舍入误差，这是由于二进制无法精确表示某些十进制小数。

生活中的例子：

浮点数就像是带小数点的温度计，可以显示36.5°C这样的温度
浮点数的精度限制就像是尺子的刻度，无法测量比最小刻度更精确的长度

// 浮点类型示例
float price = 19.99f;  // 需要f后缀
double pi = 3.14159265359;  // 更精确的小数

// 浮点数精度问题示例
System.out.println(0.1 + 0.2);  // 输出0.30000000000000004，而不是0.3

字符类型

字符类型用于表示单个字符，如字母、数字、符号等。

Java/C/C++：char
Python：没有专门的字符类型，使用长度为1的字符串

在内部，字符通常使用ASCII或Unicode编码存储。

生活中的例子：

字符就像是印刷机中的单个活字
或者像是拼音中的单个声母或韵母

// 字符类型示例
char letter = 'A';  // 单引号表示字符
char digit = '7';
char symbol = '@';

布尔类型

布尔类型只有两个可能的值：真(true)和假(false)，用于表示逻辑条件。

Java/C++/Python：boolean/bool

生活中的例子：

布尔类型就像是电灯开关，只有开和关两种状态
或者像是是非题，只有"是"和"否"两个选项

// 布尔类型示例
boolean isRaining = true;
boolean hasPassed = false;

// 在条件语句中使用
if (isRaining) {
    System.out.println("带伞");
} else {
    System.out.println("不用带伞");
}

复合数据类型

复合数据类型是由基本数据类型或其他复合数据类型组合而成的，就像分子是由原子组成的。

数组

数组是最基本的复合数据类型，用于存储同一类型的多个元素。

特点：

固定大小（在大多数语言中）
连续内存分配
通过索引快速访问元素

生活中的例子：

数组就像是一排停车位，每个位置都有编号，可以停放同类型的车辆
或者像是一栋公寓楼的门牌号，按顺序排列

// 数组示例
int[] scores = new int[5];  // 创建一个可以存储5个整数的数组
scores[0] = 95;  // 第一个元素
scores[1] = 88;
scores[2] = 72;
scores[3] = 90;
scores[4] = 83;

// 数组遍历
for (int i = 0; i < scores.length; i++) {
    System.out.println("第" + (i+1) + "个学生的分数：" + scores[i]);
}

结构体/类

结构体和类用于将不同类型的数据组合成一个单元。

C：使用struct
Java/C++/Python：使用class

生活中的例子：

结构体/类就像是一个人的档案，包含姓名、年龄、地址等不同类型的信息
或者像是一本书的信息，包含书名、作者、出版日期等

// Java中的类示例
public class Student {
    String name;
    int age;
    double gpa;
    
    // 构造函数
    public Student(String name, int age, double gpa) {
        this.name = name;
        this.age = age;
        this.gpa = gpa;
    }
}

// 使用类
Student alice = new Student("Alice", 20, 3.8);
System.out.println(alice.name + "的GPA是" + alice.gpa);

指针/引用

指针和引用用于存储内存地址，允许间接访问数据。

C/C++：使用指针（*）和引用（&）
Java/Python：只有引用，没有显式指针

生活中的例子：

指针就像是图书馆的索引卡，告诉你书在哪个书架上
或者像是遥控器，可以远程控制电视

// C语言中的指针示例
int number = 42;
int *ptr = &number;  // ptr存储number的地址

*ptr = 100;  // 通过指针修改number的值
printf("%d\n", number);  // 输出100

// Java中的引用示例
Student alice = new Student("Alice", 20, 3.8);
Student reference = alice;  // reference和alice指向同一个对象

reference.age = 21;  // 通过reference修改对象
System.out.println(alice.age);  // 输出21，因为alice和reference指向同一个对象

数据类型与数据结构的关系

数据类型是编程语言提供的基本构建块，而数据结构是我们使用这些构建块创建的更复杂的组织形式。

例如：

使用数组可以构建栈、队列等线性数据结构
使用类和引用可以构建链表、树、图等非线性数据结构

理解基本数据类型是学习数据结构的基础，就像了解砖块和水泥是学习建筑的基础一样。

1.7 本章小结

在本章中，我们介绍了数据结构与算法的基本概念、学习它们的重要性以及学习方法。

我们首先了解了什么是数据结构和算法，以及它们在解决问题中的重要作用。数据结构是组织和存储数据的方式，而算法是解决问题的步骤。

接着，我们探讨了为什么学习数据结构与算法对程序员如此重要：它们可以提升编程能力，帮助解决复杂问题，促进职业发展，并加深对计算机科学的理解。

我们还讨论了如何学习数据结构与算法，包括建立正确的学习心态和采用有效的学习方法。循序渐进、持之以恒和动手实践是成功学习的关键。

然后，我们简要介绍了计算机如何存储和处理数据，包括内存模型和数据的表示方式。这些基础知识有助于我们理解数据结构在计算机中的实现。

我们还学习了算法复杂度分析的基础知识，包括大O表示法和常见的时间复杂度。这些工具帮助我们评估和比较不同算法的效率。

最后，我们介绍了编程语言中的基本数据类型和复合数据类型，它们是构建数据结构的基础。

这些知识为我们后续学习更复杂的数据结构和算法奠定了基础。在接下来的章节中，我们将深入探讨各种具体的数据结构和算法，并学习如何在实际问题中应用它们。

1.8 练习题

解释数据结构和算法的区别和联系。
- 思考：它们各自的定义是什么？它们如何协同工作？
- 提示：可以用生活中的例子来类比，如图书馆的书架组织（数据结构）和查找书籍的方法（算法）。
为什么学习数据结构与算法对程序员很重要？
- 思考：它们如何影响代码质量、性能和解决问题的能力？
- 提示：考虑实际工作中可能遇到的场景，如处理大量数据或优化性能瓶颈。
分析以下代码片段的时间复杂度：
```
for (int i = 0; i < n; i++) {
    sum += i;
}
```
- 思考：基本操作是什么？它执行了多少次？
- 提示：关注循环的执行次数与输入规模n的关系。
分析以下代码片段的时间复杂度：
```
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        sum += i * j;
    }
}
```
- 思考：嵌套循环如何影响时间复杂度？
- 提示：分析内外层循环的执行次数及其乘积关系。
思考：在实际编程中，你遇到过哪些可以通过合理选择数据结构来优化的问题？
- 思考：不同的数据结构如何影响特定操作（如查找、插入、删除）的效率？
- 提示：考虑常见场景，如频繁查找特定元素、需要保持元素顺序、需要快速判断元素是否存在等。
手动模拟冒泡排序的过程，对数组[5, 3, 8, 4, 2]进行排序。
- 思考：每一轮比较和交换后，数组的状态是什么？
- 提示：按照冒泡排序的规则，相邻元素比较，较大的元素"冒泡"到后面。
解释计算机内存中的位、字节和字的关系。
- 思考：它们的大小关系是什么？各自在数据存储中扮演什么角色？
- 提示：考虑它们如何组织成层次结构，以及在不同数据类型中的应用。
比较数组和链表的优缺点。
- 思考：它们在内存分配、元素访问、插入删除操作上有何不同？
- 提示：考虑时间复杂度和空间使用的角度。