概述¶

数据结构是程序的骨架，而算法则是程序的灵魂。

《算法 + 数据结构 = 程序》是 Pascal 语言之父 Niklaus Emil Wirth 写过的一本非常著名的书。而作为书名的这句话也成为了计算机科学的经典名句。

大部分数据结构和算法教材，在开篇都试图会给这两个概念下一个明确的定义。但是这些定义都很抽象，对理解这两个概念并没有实质性的帮助。

从广义上讲，数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。

数据结构是计算机存储、组织数据的方式，是指相互之间存在一种或多种特定关系的数据元素的集合

数据结构和算法是相辅相成的。数据结构是为算法服务的，算法要作用在特定的数据结构之上。因此，我们无法孤立数据结构来讲算法，也无法孤立算法来讲数据结构。

算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。

算法（algorithm）是在有限时间内解决特定问题的一组指令或操作步骤，它具有以下特性。

问题是明确的，包含清晰的输入和输出定义。
具有可行性，能够在有限步骤、时间和内存空间下完成。
各步骤都有确定的含义，在相同的输入和运行条件下，输出始终相同。

数据结构（data structure）是组织和存储数据的方式，涵盖数据内容、数据之间关系和数据操作方法，它具有以下设计目标。

空间占用尽量少，以节省计算机内存。
数据操作尽可能快速，涵盖数据访问、添加、删除、更新等。
提供简洁的数据表示和逻辑信息，以便算法高效运行。

数据结构设计是一个充满权衡的过程。如果想在某方面取得提升，往往需要在另一方面作出妥协。下面举两个例子。

链表相较于数组，在数据添加和删除操作上更加便捷，但牺牲了数据访问速度。
图相较于链表，提供了更丰富的逻辑信息，但需要占用更大的内存空间。

想要学习数据结构与算法，首先要掌握一个数据结构与算法中最重要的概念——复杂度分析。

《数据结构和算法》解决的是如何更省、更快地存储和处理数据的问题，因此，我们就需要一个考量效率和资源消耗的方法，这就是复杂度分析方法。

所以，如果你只掌握了数据结构和算法的特点、用法，但是没有学会复杂度分析，那就相当于只知道操作口诀，而没掌握心法。

那么我们应该如何去衡量不同算法之间的优劣呢？主要还是从算法所占用的「时间」和「空间」两个维度去考量。

时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。
空间维度：是指执行当前算法需要占用多少存储空间，我们通常用「空间复杂度」来描述。

因此，评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而有时候，时间最优和空间最优往往是「鱼和熊掌」不可兼得，那么我们就需要从中去取一个平衡点。

同一个算法在不同的计算机上运行的速度会有一定的差别，并且实际运行速度难以在理论上进行计算，实际去测量又比较麻烦，所以我们通常考虑的不是算法运行的实际用时，而是算法运行所需要进行的基本操作的数量。

复杂度¶

复杂度分析能够体现算法运行所需的时间和空间资源与输入数据大小之间的关系。它描述了随着输入数据大小的增加，算法执行所需时间和空间的增长趋势。

"时间和空间资源"分别对应时间复杂度（time complexity）和空间复杂度（space complexity）。
"随着输入数据大小的增加"意味着复杂度反映了算法运行效率与输入数据体量之间的关系。
"时间和空间的增长趋势表示复杂度分析关注的不是运行时间或占用空间的具体值，而是时间或空间增长的"快慢"。

时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势。

// 算法 A 的时间复杂度：常数阶
void algorithm_A(int n) {
    System.out.println(0);
}
// 算法 B 的时间复杂度：线性阶
void algorithm_B(int n) {
    for (int i = 0; i < n; i++) {
        System.out.println(0);
    }
}
// 算法 C 的时间复杂度：常数阶
void algorithm_C(int n) {
    for (int i = 0; i < 1000000; i++) {
        System.out.println(0);
    }
}

算法 A 只有1个打印操作，算法运行时间不随着n增大而增长。我们称此算法的时间复杂度为“常数阶”。
算法 B 中的打印操作需要循环n次，算法运行时间随着n增大呈线性增长。此算法的时间复杂度被称为“线性阶”。
算法 C 中的打印操作需要循环很多次，虽然运行时间很长，但它与输入数据大小n无关。因此C的时间复杂度和A相同，仍为“常数阶”。

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

在普通的计算机上，加减乘除、访问变量（基本数据类型的变量，下同）、给变量赋值等都可以看作基本操作。对基本操作的计数或是估测可以作为评判算法用时的指标。

从CPU的角度来看，这段代码的每一行都执行着类似的操作：读数据——运算——写数据。

尽管每行代码对应的CPU执行的个数、执行的时间都不一样，这里只是粗略估计，假设每行代码执行的时间都一样，为unit_time。

第2、3行代码分别需要1个unit_time的执行时间，第4、5行都运行了n遍，所以共需要 2n 个 unit_time 的执行时间，所以这段代码总的执行时间就是(2n+2)个unit_time

此求和函数的操作数量与输入数据大小成正比，或者说成"线性关系"。实际上，时间复杂度描述的就是这个"线性关系"。

T(n)  = O(f(n))

T(n) 它表示代码执行的时间； n 表示数据规模的大小； f(n) 表示每行代码执行的次数总和，因为这是一个公式，所以用 f(n) 来表示。

公式中的 O ，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。第一个例子中的T(n) = O(2n+2)，第二个例子中的T(n) = O(2n 2 +2n+3)。

大O复杂度表示法

这就是大O时间复杂度表示法。大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

当 n 很大时，你可以把它想象成 10000 、 100000 。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。

我们只需要记录一个最大量级就可以了，如果用大O表示法表示刚讲的那两段代码的时间复杂度，就可以记为：T(n) = O(n)； T(n) = O(n 2 )。

时间复杂度分析¶

如何分析一段代码的时间复杂度？

只关注循环执行次数最多的一段代码

大O这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。所以我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的n的量级，就是整段要分析代码的时间复杂度。

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

其中第 2 、 3 行代码都是常量级的执行时间，与 n 的大小无关，所以对于复杂度并没有影响。循环执行次数最多的是第 4 、 5 行代码，所以这块代码要重点分析。

这两行代码被执行了 n 次，所以总的时间复杂度就是 O(n) 。

加法法则：总复杂度等于量级最大的那段代码的复杂度

在时间复杂度的概念来说，它表示的是一个算法执行效率与数据规模增长的变化趋势，所以不管常量的执行时间多大，我们都可以忽略掉。因为它本身对增长趋势并没有影响。

乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

几种常见时间复杂度实例分析¶

常量阶O(1)

O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如下面这段代码，即便有 3 行，它的时间复杂度也是 O(1)，而不是 O(3)。

int i = 8;
int j = 6;
int sum = i + j;

/* 常数阶 */
int constant(int n) {
    int count = 0;
    int size = 100000;
    for (int i = 0; i < size; i++)
        count++;
    return count;
}

只要代码的执行时间不随n的增大而增长，这样代码的时间复杂度我们都记作O(1)。

或者说，一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)

线性阶

线性阶的操作数量相对于输入数据大小。以线性级别增长。线性阶通常出现在单层循环中

/* 线性阶 */
int linear(int n) {
    int count = 0;
    for (int i = 0; i < n; i++)
        count++;
    return count;
}