数据结构入门：算法复杂度详解

数据结构与算法简介

数据结构是数据在内存中存储的格式，指相互之间存在一种或多种特定关系的数据元素集合。常见的数据结构包括数组、链表、线性表、哈希表等。

算法是指数据输入与输出时的底层实现逻辑。不同的算法可能具有不同的运行速度，但实现的功能相同。

如何学习数据结构

1. 深入理解代码逻辑。
2. 结合图示与思考进行推导。

算法效率

什么是算法效率？

算法效率指代码运行的快慢。即使最终结果相同，不同实现方式的运行效率可能存在差异。

复杂度的计算

衡量算法好坏通常从时间与空间两个维度进行：

• 时间复杂度：衡量算法运行时间的快慢。
• 空间复杂度：衡量算法运行时所需的额外空间。

时间复杂度

定义

时间复杂度是一个函数 $T(N)$，定量描述了算法的运行时间。我们不直接计算程序的实际运行时间，原因如下：

1. 相同代码在不同编译器或机器上运行时间不同。
2. 测试需要代码完成后才能进行，影响开发效率。
3. 使用 $T(N)$ 模型可大致判断代码运行效率，提高分析与书写效率。

计算原则

计算 $T(N)$ 时，通常关注程序中最坏情况下的最大运行时间。

示例分析

请计算以下 Func1 中 ++count 语句总共执行了多少次？

void Func1(int N) {
    int count = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            ++count;
        }
    }
    for (int k = 0; k < 2 * N; ++k) {
        ++count;
    }
    int M = 10;
    while (M--) {
        ++count;
    }
}

该函数的时间复杂度主要由循环次数决定。