史上最强数据结构----算法的时间复杂度和空间复杂度

第二章 算法的时间复杂度和空间复杂度

1.算法效率

如何衡量一个算法的好坏？

一般依靠算法的时间复杂度和空间复杂度来进行衡量。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计
算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

2 时间复杂度

2.1 时间复杂度的概念

定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。算法中的基本操作的执行次数，为算法的时间复杂度。

即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

例子：

问：Func1中语句++count语句共执行了多少次？

void Func1(int N)
{
    int count = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            ++count;
        }
    }

    for (int k = 0; k < 2 * N; ++k)
    {
        ++count;
    }
    int M = 10;
    while (M--)
    {
        ++count;
    }
}

执行次数用函数来表示如下：

F(N) = N^2^ + 2 * N + 10

站在数学函数的角度，2 * N +
10对函数最终运算结果的映像随着N的增大而逐渐变小，当N区域无穷大的时候我们甚至可以忽略不计，即函数的最终结果在N趋于无穷大的时候只与N2
有关。

2.2 大O的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

1. 用常数1取代运行时间中的所有加法常数(假如一个函数基本语句的执行次数是一个确定的常数的时候)。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1，则去除与这个项目相乘的常数（即去掉最高阶项的系数）。得到的结果就是大O阶。（时间复杂度衡量的是数量级）

使用大O的渐进表示法以后，Func1的时间复杂度为：

​ O(N2)

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

另外有些算法的时间复杂度存在最好、平均和最坏情况：

最坏情况：任意输入规模的最大运行次数(上界)

平均情况：任意输入规模的期望运行次数

最好情况：任意输入规模的最小运行次数(下界)

在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)。

2.3 时间复杂度的计算举例

2.3.1 实例1

// 计算Func2的时间复杂度？
void Func2(int N)
{
    int count = 0;
    for (int k = 0; k < 2 * N; ++k)
    {
        ++count;
    }
    int M = 10;
    while (M--)
    {
        ++count;
    }
    printf("%d\n", count);
}

基本操作执行了2N+10次，通过推导大O阶方法知道，时间复杂度为 O(N)。

2.3.2 实例2

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
    int count = 0;
    for (int k = 0; k < M; ++k)
    {
        ++count;
    }
    for (int k = 0; k < N; ++k)
    {
        ++count;
    }
    printf("%d\n", count);
}

基本操作执行了M+N次，有两个未知数M和N，时间复杂度为 O(N+M)

结论：时间复杂度不一定只有一个未知数，也有可能会有两个，这个根据具体参未知数来看但是如果题目中告诉我们：

1. M远大于N，此时时间复杂度就会变成O(M)。
2. M和N差不多大，此时时间复杂度就会变成O(M)或者O(N)，这两种写法均可。

2.3.3 实例3

// 计算Func4的时间复杂度？
void Func4(int N)
{
    int count = 0;
    for (int k = 0; k < 100; ++k)
    {
        ++count;
    }
    printf("%d\n", count);
}

基本操作执行了100次，通过推导大O阶方法，时间复杂度为 O(1)

2.3.4 实例4

//计算strchr的时间复杂度？
const char* strchr(const char* str, int character);

下面是这个函数的大概实现：

while(*str)
{
    if(*str == character)
        return str;
    else
        ++str;
}
return NULL;

基本操作执行最好1次，最坏N次，时间复杂度一般看最坏，时间复杂度为 O(N)

2.3.5 实例5

//计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}

注意：两层循环不一定就是O(N2)，还要看函数的具体实现。

第一次比较次数：N - 1

第二次比较次数：N - 2

第三次比较次数：N - 3

···

第N-1次比较次数：1

最坏情况：F(N) = (N*(N-1))/2

最好情况：F(N) = N - 1（比较第一轮，没有发生交换，说明所给数据是有序的，就不必继续进行排序）

复杂度：O(N2)（取最坏的情况）

2.3.6 实例6

//计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
    assert(a);
    int begin = 0;
    int end = n;
    while (begin < end)
    {
        int mid = begin + ((end - begin) >> 1);
        //用右移运算符是为了防止(end+begin)的值溢出，超出最大整数值
        if (a[mid] < x)
            begin = mid + 1;
        else if (a[mid] > x)
            end = mid;
        else
            return mid;
    }
    return -1;
}

上述代码采用了二分查找法。

上面的代码是左闭右开区间，两种写法的区别就是对于边界的处理，无论是哪种区间，都应该贯彻保持到底，下面是左闭右闭区间的二分查找法代码：

int BinarySearch(int* a, int n, int x)
{
    assert(a);
    int begin = 0;
    int end = n - 1;
    while (begin <= end)
    {
        int mid = begin + ((end - begin) >> 1);
        if (a[mid] < x)
            begin = mid + 1;
        else if (a[mid] > x)
            end = mid - 1;
        else
            return mid;
    }
    return -1;
}

最好情况：O(1)

最坏情况：

假设我们找了X次，最后只剩一个元素，我们仍然没有找到，那么

1(剩下的一个元素) * 2X = N

X = log2N

时间复杂度：O(log2N)（有的简写成logN，甚至有的还会简写成lgN，但是最后这种写法是存在误差的，也是不推荐的）

结论：要准确分析算法的思想，而不要仅看循环的层数。

2.3.7 实例7

//计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
    if (0 == N)
        return 1;

    return Fac(N - 1) * N;
}

通过计算分析发现基本操作递归了N次（当然，函数调用的次数是N+1次），时间复杂度为O(N)。

下面是上面函数的变形：

long long Fac(size_t N)
{
    if (0 == N)
        return 1;
    for(size_t i = 0;i < N;i++)
    {
        printf("%d",i);//看这个语句的执行次数
    }
    return Fac(N - 1) * N;
}

第一次函数调用：N

第二次函数调用：N - 1

···

第N次函数调用：1

第N + 1次函数调用：0（for循环无法进行，因为N = 0）

F(N) = (N + 1) * N / 2

所以时间复杂度为：O(N2)

注意：

递归算法时间复杂度计算：

1. 每次函数调用是O(1)，那么就看它的递归次数
2. 每次函数调用不是O(1)，就看它的递归调用中次数的累加。

2.3.8 实例8

//计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
    if (N < 3)
        return 1;

    return Fib(N - 1) + Fib(N - 2);
}

此时就可以使用等比数列公式进行计算(1*(1 - 2N-1))/(1-2) = 2N-1 -
1（此时我们假想的是的满的情况，其实还有没有满的地方，比如在上面右下角的地方是没有的，因为那些数相对来说比较小，到不了那）

通过计算分析发现基本操作递归了2N（将2N-1看成是2N次方）次，时间复杂度为O(2N)。

3.空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以**空间复杂度算的是变量的个数。 **

空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

3.1 实例1：

//计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}

解析：总共开辟了end、exchange、i总共三个变量，即使用了常数个额外空间，所以空间复杂度为O(1)。

3.2 实例2：

//计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
    if (n == 0)
        return NULL;

    long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
    fibArray[0] = 0;
    fibArray[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
    }
    return fibArray;
}

解析：总共动态开辟了(n+1)个整型的空间，所以空间复杂度为O(N)。

3.3 实例3：

//计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
    if (N == 0)
        return 1;

    return Fac(N - 1) * N;
}

解析： 递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)

3.4 实例4

//计算斐波那契递归Fib的空间复杂度？
long long Fib(size_t N)
{
    if (N < 3)
        return 1;

    return Fib(N - 1) + Fib(N - 2);
}

注意：时间是累计的，空间是可以复用的。

解析：调用Fib(3)后，然后先调用Fib(2)，在Fib(2)调用完后，Fib(2)的栈帧将会销毁，Fib(2)的栈帧在销毁后，继续调用Fib(1)，此时Fib(1)栈帧所用的空间和刚才Fib(2)栈帧所用的空间是同一块空间。同一层所开辟的栈帧所占的空间是同一块空间。就是说，在一个时刻上，总共开辟了N-1个栈帧，所以空间复杂度为O(N)。

举例表示：

解释：f1的栈帧空间销毁之后，f2将原来f1栈帧的空间给覆盖了。（空间的销毁只是交还使用权给系统）

4.常见复杂度对比

一般算法常见的复杂度如下：
5201314O(1)常数阶*3n + 4O(n)线性阶3n2 + 4n + 5*O(n2)平方阶3log2n + 4*O(log2n)对数阶2n + 3nlog2n + 4*O(nlog2n)nlog2n阶n3 + 2n2 + 4n + 6*O(n3)立方阶2n**O(2^n)**指数阶

复杂度对比：

O(n!) > O(2n) > O(n2) > O(nlog2n) > O(n) > O(log2n) > O(1)

5. 复杂度的oj练习

5.1 消失的数字

解决方法：

1. 排序（冒泡(N2)、qsort(nlog2N))（不符合条件）
2. 映射（下标法：每个值是多少就对应多少的下标）(O(N))，但是这种方式有O(N)的空间复杂度代码展示：``` int *ret = (int*)malloc(sizeof(int)*(numsSize+1)); int i = 0; for(i = 0;i<numsSize+1;i++) { ret[i] = -1; } for(i = 0;i<numsSize;i++) { ret[nums[i]] = nums[i]; } for(i = 0;i<numsSize+1;i++) { if(ret[i]==-1) { return i; } } return -1; } ``````
3. 异或（用一个变量value跟0~N的数据进行异或，再跟所给的数据进行异或）(O(N))``` int value = 0; int i = 0; for (i = 0; i <= numsSize; i++) { value ^= i; } for (i = 0; i < numsSize; i++) { value ^= nums[i]; } return value; } ``````
4. 等差数列公式。将0~N的和减去原数组的所有数据。(O(N))``` int sum = 0; int i = 0; int n = numsSize; sum = (n + 1) * n / 2;//等差数列的和的公式 for (i = 0; i < numsSize; i++) { sum -= nums[i]; } return sum; } ``````

5.2 旋转数组

进阶：

• 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
• 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

1. 右旋k次，一次旋转一个字符。时间复杂度：最号情况：O(N)最坏情况：O(N*K) （当然也可以写成O(N2）空间复杂度：O(1)
2. 额外开数组，将后k个放到开辟数组的前面，将前N - k个放到数组的后面。时间复杂度：O(N)(N次循环遍历移动数组元素)空间复杂度：O(N)
3. 三趟逆置：第一次：前N - K个进行逆置；第二次：对后K个进行逆置；第三次：对全体进行逆置。时间复杂度：O(N)(总共逆置了2N个元素)空间复杂度：O(1)代码：``` while(left<=right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } void rotate(int* nums, int numsSize, int k){ k%=numsSize; reverse(0,numsSize - k-1,nums); reverse(numsSize - k,numsSize-1,nums); reverse(0,numsSize - 1,nums); } ``````