本文是我在学习（程序员Carl (opens new window)）的原创作品《代码随想录》做的笔记。现上传到我的博客，大家可以去看看大佬的作品，真的很不错。

算法性能分析

时间复杂度

（1）时间复杂度

一个函数，定性描述一个算法的运行时间。

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

（2）大O

函数的渐近上界。

输入数据的形式对程序运算时间是有很大影响的，在数据本来有序的情况下时间复杂度是O(n)，但如果数据是逆序的话，插入排序的时间复杂度就是，也就对于所有输入情况来说，最坏是的时间复杂度，所以称插入排序的时间复杂度为。快速排序是，但是当数据已经有序情况下，快速排序的时间复杂度是的，所以严格从大O的定义来讲，快速排序的时间复杂度应该是。但是我们依然说快速排序是的时间复杂度，这个就是业内的一个默认规定，这里说的代表的就是一般情况，而不是严格的上界。

（3）不同数据规模下不同时间复杂度的时间

从上图可以只看出再决定使用什么算法时，并不是时间复杂度越低越好，这和输入数据的规模有很大的关系。为什么会出现这种情况呢？这就关系到大的定义：数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度，这个数据量也就是常数项系数已经不起决定性作用的数据量。

通常时间复杂度的排序如下：

$常数阶对数阶线性阶线性对数阶平方阶立方阶指数阶$

注意这里的不一定以2为底，这是忽略底数的描述。

计算机的性能决定算法花费的时间

计算机的运算速度主要看CPU的配置，以2015年MacPro为例，CPU配置：2.7 GHz Dual-Core Intel Core i5 。也就是 2.7 GHz 奔腾双核，i5处理器，GHz是指什么呢，1Hz = 1/s，1Hz 是CPU的一次脉冲（可以理解为一次改变状态，也叫时钟周期），称之为为赫兹。

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

所以 1GHz = 10亿Hz，表示CPU可以一秒脉冲10亿次（有10亿个时钟周期），但是并不是一个时钟周期就是一次CPU运算。

例如1 + 2 = 3，cpu要执行四次才能完整这个操作，步骤一：把1放入寄存机，步骤二：把2放入寄存器，步骤三：做加法，步骤四：保存3。而且计算机的cpu也不会只运行我们自己写的程序上，同时cpu也要执行计算机的各种进程任务等等，我们的程序仅仅是其中的一个进程而已。

递归的时间复杂度

同一个问题可以写出和的代码。这里有一些例子。求x的n次方。

的直观算法

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

的递归算法1

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

递归算法的时间复杂度的本质是**递归的次数*每次递归的操作次数**。这里每次递归进行一次一次乘法操作，所以时间复杂度是。

的递归算法2

int function3(int x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;

    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为例：

这颗满二叉树的节点数量是。

若满二叉树的深度为（从0开始），则有个节点，其中。故忽略常数项-1后，时间复杂度为。

的递归算法

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

这里把相同的递归调用提取出来只进行一次递归，保存副本值用于后面的计算，乘法次数为递归树的高度，大大提高了效率。

空间复杂度

对算法在运行过程中占用内存空间大小的量度，记做。用来对程序运行中需要的空间进行估计。编译器的内存对齐，编程语言容器的底层实现等都会影响程序真正的内存开销。

的空间复杂度

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

程序开销的内存不会随的变化而变化。表示为。

的空间复杂度

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

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

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

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

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

时间复杂度和空间复杂度分析

以为例，递归树如图：

由于一棵二叉树的深度为(根节点深度为1)可以有个节点。故时间复杂度为。

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

由于每次递归都需要栈里，到达递归最深处时就开始弹出，又每次递归需要常数空间，所以空间复杂度为。

// 版本二
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);
    }
}