最近在学习数据结构与算法，发现对于算法的时间和空间复杂度一直处于一个比较懵懂的状态，所以专门写一下来理清楚这两个概念。在这之前，我们需要先了解一些基本概念。

1. 基本概念与术语

1.1 数据结构

  • 在计算机中，数据并不是孤立、杂乱无序的，而是具有内在联系的数据集合。数据之间存在的一种或多种特定关系，也就是数据的组织形式；
  • 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合；
  • 简单的理解就是关系，比如分子结构；
  • 我们分析这些关系的目的就是为了编写出一个 “好” 的程序。

按照视点的不同，我们一般把数据结构分为「逻辑结构」和「物理结构」。

1.2 逻辑结构

逻辑结构是指数据元素之间的相互关系，分为以下四种。每个数据元素看为一个节点，如下面图中的①~⑨。

1.2.1 集合结构

集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系，类似于数学中的集合。

1.2.2 线性结构

线性结构中的数据元素之间是「一对一」的关系。

1.2.3 树型结构

树形结构中的数据元素之间存在一种「一对多」的层次关系。

1.2.4 图型结构

图形结构的数据元素是「多对多」的关系。

1.3 物理结构

物理结构指数据的逻辑结构在计算机中的存储形式，难点也在这里，物理结构应该正确的存储数据元素之间的关系，分为「顺序存储」和「链式存储」。

1.3.1 顺序存储

顺序存储是指把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。这种存储方式不利于频繁变化的结构，如：数据频繁的插入和删除。

1.3.2 链式存储

对于时常要变化的结构，应该使用链式存储，链式存储是指把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。我们通过数据元素包含指针，而指针存放与其相关联的数据元素的地址来表示它们之间的逻辑关系。

2. 算法定义

数据结构通常是和算法一起的，抛开任何一个单独谈论都是不科学的，它们的一起出现是为了解决现实中的一些复杂问题。

  • 算法是解决特定问题求解步骤的描述；
  • 算法注重的是思想，比如：排序、找到最大数和最小数；
  • 对于给定的问题，可以有多种算法来解决；
  • 算法具有优劣之分，除基本的正确性、可读性、健壮性外，好的算法还应该具备「耗时少，高效率」和「占用存储量低」的特点。

3. 算法效率

正所谓 “是骡子是马，拉出来遛遛”，一个好的算法才能够禁得起检验。我们一般通过「事前分析估算方法」来对「算法的运行时间」和「占用内存的大小」进行估算。

通常一个程序在计算机上运行所消耗的时间取决于下列因素：

  • 算法采用的策略、方法；
  • 编译产生的代码质量；
  • 问题的输入规模；
  • 机器执行指令的速度。

抛开和硬件、软件相关的影响因素，一个程序的运行时间，依赖于算法的好坏和问题的输入规模。我们习惯用「时间复杂度」预估算法的执行时间，用「空间复杂度」预估算法占用的内存大小。

3.1 时间复杂度

因为运行时间越短算法效率越高，而 CPU 操作每个单元运行所消耗的时间（这里记为BTime）都是相同的，我们就可以通过估算算法操作单元的数量（操作数）来估算该算法消耗的时间。

假设算法输入的规模为 n，用 T(n) 来表示算法所消耗的时间，f(n) 为操作数，那么：

因为 $BTime$ 是一个确定的常量，那么随着输入规模 n 的增大， T(n) 的增长率一定和 f(n) 的增长率相同，我们把这个增长趋势称为时间复杂度，使用大 O 阶表示法记为 O(f(n))。

一般情况下 T(n) 增长越慢的算法为最优算法，所以预估算法的执行时间转变为计算算法的 O(f(n)) ，也就是计算时间复杂度。

3.2 大 O 阶表示法

我们使用 O(f(n)) 来表示一个算法的时间复杂度，严格来说，O(f(n)) 表示的是算法以最坏的情况运行的时间复杂度，但日常中默认指的是一般情况下的时间复杂度。

3.3 推导大 O 阶

说白了就是省略 f(n) 的过程

  • 用常数 1 取代运行时间中的所有加法常数；
  • 只保留最高阶项；
  • 如果最高阶项存在且不是 1，则去除与这个项相乘的常数。

因为输入规模 n 在突破一个点后，常数项和常数项系数（如：O(100n) 中的 100）已经起不了决定性的作用了，所以直接忽略。

需要注意的是：

  • 在决定使用哪些算法的时候，不是时间复杂越低的越好（因为简化后的时间复杂度忽略了常数项等等）；
  • 我们省略常数项系数是因为一般情况下都是默认数据规模足够的大；
  • 如果常数项系数非常大，例如10^7 ，那么常数项系数应该考虑保留。

基于以上默认规则和事实，得出以下排行：

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)立方阶 < O(2^n)指数阶

举例：

1
2
3
4
5
6
7
8
9
int i, j;
for (i = 0; i < n; i++)
{
    /* 注意j = i 而不是0 */
    for (j = i; j < n; j++) 
    {
        /* 时间复杂度为O(1)的程序步骤序列 */
    }
}

由于当 i=0 时，内循环执行了 n 次，当 i=1 时，执行了 n-1 次，……当 i=n-1 时，执行了1次。所以总的执行次数为：

那么根据上面的规则可以得出该算法的时间复杂度为 O(n^2)。

3.4 空间复杂度

空间复杂度 S(n) 是指算法在运行过程中所申请的内存空间的量度，也使用 O(f(n))来表示，此时的 f(n) 为输入规模 n 与 算法申请的内存空间的关系。

比如：

1
2
3
4
int j = 0;
for (int i = 0; i < n; i++) {
    j++;
}

此时，如果是 JAVA 语言，因为 j 指向是一个常量，常量虽然在随 n 变化，但是并没有新的变量也就不需要再去分配内存空间，所以上面算法的空间复杂度为 O(1)。

不同的编程语言有各自的内存管理方式。

  • C/C++这种内存堆空间的申请和释放完全靠自己管理；
  • Java 依赖JVM来做内存管理；
  • Python内存管理是由私有堆空间管理的，所有的python对象和数据结构都存储在私有堆空间中。

以下是基本数据类型占用的内存大小：

安装 64 位的操作系统的计算机内存都已经超过了4G，也就是指针大小如果还是4个字节的话，就已经不能寻址全部的内存地址，所以64位编译器使用8个字节的指针才能寻找所有的内存地址。