Leslie Shang's Blog
Posts Tags Categories Links About
Leslie Shang's Blog

Contents

Algorithm performance analysis

Leslie Shang included in Algorithm
   1488 words   7 minutes    views  

时间复杂度分析

什么是时间复杂度

时间复杂度是一个函数，它定性描述该算法的运行时间。

在软件开发中，时间复杂度就是用来方便开发者估算出程序运行的时间。

通常会估算算法的操作单元数量来代表程序消耗的时间，这里默认CPU的每个单元运行消耗的时间都是相同的。

假设算法的问题规模为 n，那么操作单元数量便用函数 f(n) 来表示，随着数据规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同，这称作为算法的渐近时间复杂度，简称时间复杂度，记为 O(f(n))。

什么是大O

算法导论给出的解释：大O用来表示上界的，用它作为算法在最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。

输入数据的形式对程序运算时间是有很大影响的。

同样算法导论给出了例子：

插入排序的时间复杂度是 O(n$^2$) 。在数据本来有序的情况下插入排序时间复杂度是 O(n)，但如果数据是逆序的话，插入排序的时间复杂度就是 O(n$^2$)，也就对于所有输入情况来说，最坏是 O(n$^2$) 的时间复杂度，所以称插入排序的时间复杂度为 O(n$^2$)。

同理快速排序的时间复杂度是 O(nlogn)，但是当数据已经有序情况下，快速排序的时间复杂度是 O(n$^2$) 的，所以严格从大O的定义来讲，快速排序的时间复杂度应该是 O(n$^2$)。

但是依然认为快速排序是 O(nlogn) 的时间复杂度，这个就是一个默认规定，这里说的 O 代表的就是一般情况，而不是严格的上界。

如图所示：

/images/2023-02-22-算法性能分析/1

不同数据规模的差异

如下图中可以看出不同算法的时间复杂度在不同数据输入规模下的差异。

/images/2023-02-22-算法性能分析/2

在决定使用哪些算法的时候，不是时间复杂越低的越好（因为简化后的时间复杂度忽略了常数项等等），要考虑数据规模，如果数据规模很小甚至可以用 O(n$^2$) 的算法比 O(n) 的更合适（在有常数项的时候）。

就像上图中 O(5n$^2$) 和 O(100n) 在 n 为20之前很明显 O(5n$^2$) 是更优的，所花费的时间也是最少的。

为什么在计算时间复杂度的时候要忽略常数项系数呢，也就说 O(100n) 就是 O(n) 的时间复杂度，O(5n$^2$) 就是 O(n$^2$) 的时间复杂度，而且要默认 O(n) 优于 O(n$^2$) 呢？

这里就又涉及到大O的定义，因为大O就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度，这个数据量也就是常数项系数已经不起决定性作用的数据量。

例如上图中20就是那个点，n 只要大于20，常数项系数已经不起决定性作用了。

所以时间复杂度都是省略常数项系数的，因为一般情况下都是默认数据规模足够的大，基于这样的事实，给出的算法时间复杂的的一个排行如下所示：

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

但是也要注意大常数，如果这个常数非常大，例如10$^7$，10$^9$，那么常数就是不得不考虑的因素了。

复杂表达式的化简

有时候计算时间复杂度的时候发现不是一个简单的 O(n) 或者 O(n$^2$)，而是一个复杂的表达式，例如：

1

O(2*n^2 + 10*n + 1000)

通过简化法描述这个算法的时间复杂度。

  1. 去掉运行时间中的加法常数项（因为常数项并不会因为 n 的增大而增加计算机的操作次数）
  2. 去掉常数系数
  3. 只保留保留最高项，去掉数量级小一级的 n（因为 n$^2$ 的数据规模远大于 n ）

最终简化为：

1

O(n^2)

所以最后这个算法的算法时间复杂度是 O(n$^2$) 。

O(logn) 中的 log 是以什么为底？

平时说这个算法的时间复杂度是 logn 的，不一定是 log 以2为底 n 的对数，也可以是以10为底 n 的对数，也可以是以20为底 n 的对数，但统一说 logn，也就是忽略底数的描述。

/images/2023-02-22-算法性能分析/3

在时间复杂度的计算过程中，log以 i 为底 n 的对数等于 log 以 j 为底 n 的对数，所以忽略了 i，直接说是 logn。

举例计算时间复杂度

题目描述：找出 n 个字符串中相同的两个字符串（假设这里只有两个相同的字符串）。

如果是暴力枚举的话，时间复杂度是多少呢，是O(n$^2$)么？

这里存在字符串比较的时间消耗，并不像 int 型数字做比较那么简单，除了 n$^2$ 次的遍历次数外，字符串比较依然要消耗 m 次操作（ m 也就是字母串的长度），所以时间复杂度是 O(m × n × n)。

其他解题思路：

先对 n 个字符串按字典序来排序，排序后 n 个字符串就是有序的，意味着两个相同的字符串就是挨在一起，然后在遍历一遍 n 个字符串，这样就找到两个相同的字符串了。

那看看这种算法的时间复杂度，快速排序时间复杂度为 O(nlogn)，依然要考虑字符串的长度是m，那么快速排序每次的比较都要有 m 次的字符比较的操作，就是 O(m × n × logn)。

之后还要遍历一遍这 n 个字符串找出两个相同的字符串，遍历的时候依然要比较字符串，所以总共的时间复杂度是 O(m × n × logn + n × m)。

对 O(m × n × log n + n × m) 进行简化操作，把 m × n 提取出来变成 O(m × n × (logn + 1))，再省略常数项最后的时间复杂度是 O(m × n × log n)。

最后很明显 O(m × n × logn) 要优于 O(m × n × n)！

所以先把字符串集合排序再遍历一遍找到两个相同字符串的方法要比直接暴力枚举的方式更快。

这就是通过分析两种算法的时间复杂度得来的。

估计程序运行时间

计算机的运算速度主要看CPU的配置，以 Intel Core i7-12700K 为例，CPU主频 3.6GHz。

1Hz = 1/s，1Hz 是CPU的一次脉冲（可以理解为一次改变状态，也叫时钟周期），称之为赫兹，那么 1GHz 等于多少赫兹呢

  • 1GHz = 1000MHz（兆赫）
  • 1MHz（兆赫）= 1百万赫兹

所以 1GHz = 10亿Hz，表示CPU可以一秒脉冲10亿次（有10亿个时钟周期），这里不要简单理解一个时钟周期就是一次CPU运算。

例如1 + 2 = 3，CPU要执行四次才能完整这个操作，步骤一：把1放入寄存机，步骤二：把2放入寄存器，步骤三：做加法，步骤四：保存3。

而且计算机的CPU也不会只运行我们自己写的程序上，同时CPU也要执行计算机的各种进程任务等等，我们的程序仅仅是其中的一个进程而已。

  • CPU执行每条指令所需的时间实际上并不相同，例如CPU执行加法和乘法操作的耗时实际上都是不一样的。
  • 现在大多计算机系统的内存管理都有缓存技术，所以频繁访问相同地址的数据和访问不相邻元素所需的时间也是不同的。
  • 计算机同时运行多个程序，每个程序里还有不同的进程线程在抢占资源。

尽管有很多因素影响，但是还是可以对自己程序的运行时间有一个大体的评估的。

引用算法4里面的一段话：

  • 火箭科学家需要大致知道一枚试射火箭的着陆点是在大海里还是在城市中；
  • 医学研究者需要知道一次药物测试是会杀死还是会治愈实验对象；

所以任何开发计算机程序员的软件工程师都应该能够估计这个程序的运行时间是一秒钟还是一年。

写测试程序测 1s 内处理多大数量级数据：

C++ 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <iostream>
#include <chrono>
#include <thread>
using namespace std;
using namespace chrono;
// O(n)
void function1(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        k++;
    }
}

// O(n^2)
void function2(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        for (long j = 0; j < n; j++) {
            k++;
        }
    }

}
// O(nlogn)
void function3(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        for (long long j = 1; j < n; j = j*2) { // 注意这里j=1
            k++;
        }
    }
}
int main() {
    long long n; // 数据规模
    while (1) {
        cout << "输入n：";
        cin >> n;
        milliseconds start_time = duration_cast<milliseconds >(
            system_clock::now().time_since_epoch()
        );
        function1(n);
//        function2(n);
//        function3(n);
        milliseconds end_time = duration_cast<milliseconds >(
            system_clock::now().time_since_epoch()
        );
        cout << "耗时:" << milliseconds(end_time).count() - milliseconds(start_time).count()
            <<" ms"<< endl;
    }
}

Java 版本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

import java.util.Scanner;

public class TimeComplexity {
    // o(n)
    public static void function1(long n) {
        System.out.println("o(n)算法");
        long k = 0;
        for (long i = 0; i < n; i++) {
            k++;
        }
    }

    // o(n^2)
    public static void function2(long n) {
        System.out.println("o(n^2)算法");
        long k = 0;
        for (long i = 0; i < n; i++) {
            for (long j = 0; j < n; j++) {
                k++;
            }
        }
    }

    // o(nlogn)
    public static void function3(long n) {
        System.out.println("o(nlogn)算法");
        long k = 0;
        for (long i = 0; i < n; i++) {
            for (long j = 1; j < n; j = j * 2) { // 注意这里j=1
                k++;
            }
        }
    }

    public static void main(String[] args) {
        while(true) {
            Scanner in = new Scanner(System.in);
            System.out.print("输入n: ");
            int n = in.nextInt();
            long startTime = System.currentTimeMillis();

            function1(n);
            // function2(n);
            // function3(n);

            long endTime = System.currentTimeMillis();
            long costTime = endTime - startTime;
            System.out.println("算法耗时 == " + costTime + "ms");
        }
    }
}

递归算法的时间复杂度

递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归的时间复杂度。

空间复杂度分析

什么是空间复杂度

是对一个算法在运行过程中占用内存空间大小的量度，记做 S(n)=O(f(n)。

空间复杂度 (Space Complexity) 记作 S(n) 依然使用大O来表示。利用程序的空间复杂度，可以对程序运行中需要多少内存有个预先估计。

空间复杂度是考虑程序运行时占用内存的大小，而不是可执行文件的大小。

举例说明

  1. 空间复杂度 O(1)

    1
2
3
4

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

    随着 n 的变化，所需开辟的内存空间并不会随着 n 的变化而变化。即此算法空间复杂度为一个常量，所以表示为大O(1)。

  2. 空间复杂度 O(n)

    当消耗空间和输入参数 n 保持线性增长，这样的空间复杂度为 O(n)。

    1
2
3
4

    int* a = new int(n);
for (int i = 0; i < n; i++) {
    a[i] = i;
}

    定义了一个数组，这个数组占用的大小为 n，虽然有一个 for 循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，随着 n 的增大，开辟的内存大小呈线性增长，即 O(n)。

空间复杂度O(n$^2$)，O(n$^3$) 可以以此例举，空间复杂度是 logn 的情况确实有些特殊，是在递归的时候，会出现空间复杂度为 logn 的情况。

递归算法的空间复杂度

递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度

递归算法的时间与空间复杂度分析

1. 题目：求 x 的 n 次方

最直观的方式应该就是，一个 for 循环求出结果，代码如下：

1
2
3
4
5
6
7

int function1(int x, int n) {
    int result = 1;  // 注意 任何数的0次方等于1
    for (int i = 0; i < n; i++) {
        result = result * x;
    }
    return result;
}

时间复杂度为 O(n)

有没有效率更好的算法呢？

递归算法1

1
2
3
4
5
6

int function2(int x, int n) {
    if (n == 0) {
        return 1; // return 1 同样是因为0次方是等于1的
    }
    return function2(x, n - 1) * x;
}

递归算法的时间复杂度本质上是要看：递归的次数 * 每次递归中的操作次数。

那再来看代码，这里递归了几次呢？

每次 n-1，递归了 n 次时间复杂度是 O(n)，每次进行了一个乘法操作，乘法操作的时间复杂度一个常数项 O(1)，所以这份代码的时间复杂度是 n × 1 = O(n)。

这个时间复杂度和之前 for 循环一样。

递归算法2

1
2
3
4
5
6
7
8
9

int function3(int x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 1) {
        return function3(x, n / 2) * function3(x, n / 2)*x;
    }
    return function3(x, n / 2) * function3(x, n / 2);
}

首先看递归了多少次，可以把递归抽象出一棵满二叉树。可以用一棵满二叉树来表示（为了方便表示，选择n为偶数16），如图：

/images/2023-02-22-算法性能分析/4

当前这棵二叉树就是求 x 的 n 次方，n 为16的情况。

这棵树上每一个节点就代表着一次递归并进行了一次相乘操作，所以递归次数等于节点个数。

这棵满二叉树的节点数量就是 2$^3$ + 2$^2$ + 2$^1$ + 2$^0$ = 15。

这么如果是求 x 的 n 次方，这个递归树有多少个节点呢，如下图所示：(m 为深度，从0开始)

/images/2023-02-22-算法性能分析/5

时间复杂度忽略掉常数项-1之后，这个递归算法的时间复杂度依然是 O(n)。

O(logn) 的递归算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int function4(int x, int n) {
    if (n == 0) {
        return 1;
    }
    int t = function4(x, n / 2);// 这里相对于function3，是把这个递归操作抽取出来
    if (n % 2 == 1) {
        return t * t * x;
    }
    return t * t;
}

这里仅仅有一个递归调用，且每次都是 n/2 ，所以这里一共调用了 log 以2为底 n 的对数次。

每次递归了做都是一次乘法操作，这也是一个常数项的操作，那么这个递归算法的时间复杂度才是真正的 O(logn)。

空间复杂度：O(logn)

2. 递归求斐波那契数列的性能分析

1
2
3
4
5

int fibonacci(int i) {
       if(i <= 0) return 0;
       if(i == 1) return 1;
       return fibonacci(i-1) + fibonacci(i-2);
}

时间复杂度分析

递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归的时间复杂度。

可以看出上面的代码每次递归都是 O(1) 的操作。再来看递归了多少次，这里将i为5作为输入的递归过程 抽象成一棵递归树，如图：

/images/2023-02-22-算法性能分析/6

可以看出树的深度 m = n (问题规模)

一棵深度（按根节点深度为1）为 m 的二叉树最多可以有 2$^m$ - 1 个节点。

所以该递归算法的时间复杂度为 O(2$^n$)，这个复杂度是非常大的，随着 n 的增大，耗时是指数上升的。

所以这种求斐波那契数的算法看似简洁，其实时间复杂度非常高，一般不推荐这样来实现斐波那契。

其实罪魁祸首就是这里的两次递归，导致了时间复杂度以指数上升。

1

return fibonacci(i-1) + fibonacci(i-2);

优化这个递归算法，主要是减少递归的调用次数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// 版本二
int fibonacci(int first, int second, int n) {
    if (n <= 0) {
        return 0;
    }
    if (n < 3) {
        return 1;
    }
    else if (n == 3) {
        return first + second;
    }
    else {
        return fibonacci(second, first + second, n - 1);
    }
}

first 和 second 初始都为1，

这里相当于用 first 和 second 来记录当前相加的两个数值，此时就不用两次递归了。

因为每次递归的时候 n 减1，即只是递归了 n 次，所以时间复杂度是 O(n)。

代码（版本二）的时间复杂度为 O(n)。

空间复杂度分析

递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度

为什么要求递归的深度呢？

因为每次递归所需的空间都被压到调用栈里（这是内存管理里面的数据结构，和算法里的栈原理是一样的），一次递归结束，这个栈就是就是把本次递归的数据弹出去。所以这个栈最大的长度就是递归的深度。

此时分析这段递归的空间复杂度，从代码中可以看出每次递归所需要的空间大小都是一样的，所以每次递归中需要的空间是一个常量，并不会随着 n 的变化而变化，每次递归的空间复杂度就是 O(1)。

递归的深度如图所示：

/images/2023-02-22-算法性能分析/7

递归第 n 个斐波那契数的话，递归调用栈的深度就是 n。

那么每次递归的空间复杂度是 O(1)， 调用栈深度为 n，所以这段递归代码的空间复杂度就是 O(n)。

最后对各种求斐波那契数列方法的性能做一下分析：

/images/2023-02-22-算法性能分析/8

可以看出，求斐波那契数的时候，使用递归算法并不一定是在性能上是最优的，但递归确实简化的代码层面的复杂度。

3. 二分法（递归实现）的性能分析

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int binary_search( int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binary_search(arr, l, mid - 1, x);
        return binary_search(arr, mid + 1, r, x);
    }
    return -1;
}

二分查找的时间复杂度是 O(logn)

空间复杂度 = 每次递归的空间复杂度和递归的深度

每次递归的空间复杂度可以看出主要就是参数里传入的这个 arr 数组，但需要注意的是在 C/C++ 中函数传递数组参数，不是整个数组拷贝一份传入函数而是传入的数组首元素地址。

也就是说每一层递归都是公用一块数组地址空间的，所以每次递归的空间复杂度是常数即：O(1)。

再来看递归的深度，二分查找的递归深度是 logn ，递归深度就是调用栈的长度，那么这段代码的空间复杂度为 1 * logn = O(logn)。

注意自己所用的语言在传递函数参数的时，是拷贝整个数值还是拷贝地址，如果是拷贝整个数值那么该二分法的空间复杂度就是 O(nlogn)。

代码的内存消耗

不同语言的内存管理

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

  • C/C++ 这种内存堆空间的申请和释放完全靠自己管理
  • Java 依赖 JVM 来做内存管理，不了解 JVM 内存管理的机制，很可能会因一些错误的代码写法而导致内存泄漏或内存溢出
  • Python 内存管理是由私有堆空间管理的，所有的 python 对象和数据结构都存储在私有堆空间中。程序员没有访问堆的权限，只有解释器才能操作。

例如 Python 万物皆对象，并且将内存操作封装的很好，所以python的基本数据类型所用的内存会要远大于存放纯数据类型所占的内存，例如，我们都知道存储 int 型数据需要4个字节，但是在 Python 中 int 类型所用空间至少为 28 字节，要远大于4个字节。

/images/2023-02-22-算法性能分析/9

int 类型，每2$^{30}$ 增加4个字节。

C++ 的内存管理

以C++ 为例来介绍一下编程语言的内存管理。

如果写C++的程序，就要知道栈和堆的概念，程序运行时所需的内存空间分为固定部分和可变部分，如下：

/images/2023-02-22-算法性能分析/10

固定部分的内存消耗是不会随着代码运行产生变化的，可变部分则是会产生变化的。

更具体一些，一个由 C/C++ 编译的程序占用的内存分为以下几个部分：

  • 栈区(Stack)：由编译器自动分配释放，存放函数的参数值，局部变量的值等，其操作方式类似于数据结构中的栈。
  • 堆区(Heap)：一般由程序员分配释放，若程序员不释放，程序结束时可能由 OS 收回。
  • 未初始化数据区(Uninitialized Data)：存放未初始化的全局变量和静态变量。
  • 初始化数据区(Initialized Data)：存放已经初始化的全局变量和静态变量。
  • 程序代码区(Text)：存放函数体的二进制代码。

代码区和数据区所占空间都是固定的，而且占用的空间非常小，那么看运行时消耗的内存主要看可变部分。

在可变部分中，栈区间的数据在代码块执行结束之后，系统会自动回收，而堆区间数据是需要程序员自己回收，所以也就是造成内存泄漏的发源地。

而 Java、Python 的话则不需要程序员去考虑内存泄漏的问题，虚拟机都做了这些事情。

Java 的内存管理

Java虚拟机(JVM)在应用在执行的过程中将自己管理的内存分为5部分：方法区，堆，虚拟机栈，本地方法栈，程序计数器

从逻辑上可将 JVM 内存分为5个部分，分为被所有线程共享的内存区域和仅被当前线程独占的内存区域，其中线程共享的内存区域包括堆和方法区，线程独占的内存区域包括虚拟机栈，本地方法栈，程序计数器。

/images/2023-02-22-算法性能分析/11

在写程序时，需要判断当前数据读写的是存在于哪类内存区域，如果存在的是线程共享的内存区域，那么就要考虑是否存在线程安全问题，如果存在线程独占的内存区域，那么就可以打消这种顾虑。

程序计数器：是线程私有的，表示代码执行到哪里，通过改变这个计数器的值来选取下一条需要执行的字节码指令，该内存是唯一一个不会发生内存溢出的地方如果线程正在执行的是一个 Java 方法，这个计数器记录的是正在执行的虚拟机字节码指令的地址；如果正在执行的是 Native 方法，这个计数器值则为空（Undefined）。

虚拟机栈：就是我们平时说的堆栈中的栈，是线程私有的，表示的是方法的内存模型，保存着局部变量表，操作数栈，方法出口等信息；在执行每个方法时会创建栈帧，方法的执行就是栈帧的入栈和出栈。

本地方法栈：本地方法栈 Native Method Statck，非 Java 语言实现的函数，往往是由 C/C++ 编写的，和操作系统相关性比较强的底层函数；其实本地方法栈就是用来支持本地方法调用逻辑的。

方法区：方法区又称永久代，非堆，此区域保存的是类信息、常量、静态变量，是线程共享的。

堆：堆内存是我们比较关心的，它是 GC 的主要区域，是线程共享的，此内存区域的唯一目的就是存放对象实例，几乎所有的对象实例都在这里分配内存，Java 堆中还可以细分为：新生代和老年代；再细致一点的有 Eden 空间、From Survivor 空间、To Survivor 空间等。可以通过 -Xmx 和 -Xms 控制此内存的大小。

如何计算程序占用多大内存

想要算出自己程序会占用多少内存就一定要了解自己定义的数据类型的大小，如下：

/images/2023-02-22-算法性能分析/12

注意图中有两个不一样的地方，为什么64位的指针就占用了8个字节，而32位的指针占用4个字节呢？

1个字节占8个比特，那么4个字节就是32个比特，可存放数据的大小为2$^{32}$，也就是4G空间的大小，即：可以寻找4G空间大小的内存地址。

大家现在使用的计算机一般都是64位了，所以编译器也都是64位的。

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

注意2$^{64}$是一个非常巨大的数，对于寻找地址来说已经足够用了。

内存对齐

不是只有 C/C++ 才会有内存对齐，只要可以跨平台的编程语言都需要做内存对齐，Java、Python 都是一样的。

存在内存对齐主要有两个原因：

  1. 平台原因：不是所有的硬件平台都能访问任意内存地址上的任意数据，某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。为了同一个程序可以在多平台运行，需要内存对齐。
  2. 硬件原因：经过内存对齐后，CPU 访问内存的速度大大提升。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

struct node{
   int num;
   char cha;
}st;
int main() {
    int a[100];
    char b[100];
    cout << sizeof(int) << endl;
    cout << sizeof(char) << endl;
    cout << sizeof(a) << endl;
    cout << sizeof(b) << endl;
    cout << sizeof(st) << endl;
}

结果为：

1
2
3
4
5

4
1
400
100
8

CPU 读取内存不是一次读取单个字节，而是一块一块的来读取内存，块的大小可以是2，4，8，16个字节，具体取多少个字节取决于硬件。

假设 CPU 把内存划分为4字节大小的块，要读取一个4字节大小的 int 型数据，来看一下这两种情况下CPU的工作量：

第一种就是内存对齐的情况，如图：

/images/2023-02-22-算法性能分析/13

一字节的 char 占用了四个字节，空了三个字节的内存地址，int 数据从地址4开始。

此时，直接将地址4，5，6，7处的四个字节数据读取到即可。

第二种是没有内存对齐的情况如图：

/images/2023-02-22-算法性能分析/14

char 型的数据和 int 型的数据挨在一起，该 int 数据从地址1开始，那么 CPU 想要读这个数据的话来看看需要几步操作：

  1. 因为 CPU 是四个字节四个字节来寻址，首先 CPU 读取0，1，2，3处的四个字节数据
  2. CPU 读取4，5，6，7处的四个字节数据
  3. 合并地址1，2，3，4处四个字节的数据才是本次操作需要的int数据

此时一共需要两次寻址，一次合并的操作。

内存对齐会浪费内存资源，但事实上，相对来说计算机内存资源一般都是充足的，我们更希望的是提高运行速度。

编译器一般都会做内存对齐的优化操作，也就是说当考虑程序真正占用的内存大小的时候，也需要认识到内存对齐的影响。

Updated on 2023-02-22
Read Markdown
 C++, java, Time Complexity, Space Complexity, Memory Management
Back | Home