1 时间复杂度

1.1 知识点

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

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

大O用来表示上界，就是对任意数据输入算法的运行时间的上界。数据用例不一样，时间复杂度也会不同。

面试中算法的时间复杂度指的都是一般情况：

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

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

1.2 例子

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

解法一：暴力枚举，时间复杂度是O(m × n × n)

解法二：先排序再遍历（两个相同的字符串挨在一起），总共的时间复杂度是 O(m × n × logn + n × m)，简化后是O(m × n × log n)

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

2 算法超时

一般OJ超时时间是1s，如果是$O(n)$的算法 ，可估算出n是多大的时候算法会超时 ⇒ 考虑log(n)解法

3 递归的时间复杂度

题目：求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;
}

时间复杂度为O(n)

解法二：

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

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

时间复杂度为 n × 1 = O(n)

解法三：

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：

这棵树上每一个节点就代表着一次递归并进行了一次相乘操作。如果是求x的n次方，这个递归树的节点计算如下图所示(m为深度，从0开始)：

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

解法四：

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;
}

这里仅仅有一个递归调用，且每次都是n/2 ，所以这里我们一共调用了$log_2n$次，每次递归都做了一次乘法操作，也是一个常数项的操作**，那么这个递归算法的时间复杂度才是真正的O(logn)**

4 空间复杂度

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

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

！空间复杂度是预先大体评估程序内存使用的大小，而不是准确算出内存

空间复杂度O(1)：

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

随着n的变化，所需开辟的内存空间并不随着n的变化而变化，算法空间复杂度为一个常量。

空间复杂度O(n)：

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

定义的数组大小为n，开辟的内存大小和输入参数n保持线性增长。

在递归的时候，会出现空间复杂度为logn的情况。

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

5 递归算法的性能分析

5.1 求斐波那契数

解法一：

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

一棵深度为k（按根节点深度为1）的二叉树最多可以有 $2^k - 1$ 个节点，该算法时间复杂度为$O(2^n)$

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

解法二：

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来记录当前相加的两个数值，不用两次递归；递归了n次，时间复杂度是 O(n)

同理递归的深度依然是n，每次递归所需的空间是常数，空间复杂度是O(n)

解法三（非递归）：

int fibonacci(int n) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        int prev = 0;
        int curr = 1;
        for (int i = 2; i <= n; ++i) {
            int next = prev + curr;
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

5.2 二分查找法

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)

空间复杂度看每次递归的空间复杂度和递归深度。需要注意在C/C++中函数传递数组参数，不是整个数组拷贝一份而是传入数组首元素地址，每一层递归都公用一块数组地址空间。所以每次递归的空间复杂度是常数O(1)。递归深度是logn，空间复杂度为 1 * logn = O(logn)。

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

6 内存对齐

为什么会有内存对齐？

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

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

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

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

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