【数据结构】复杂度分析

目录

一、算法

1.基本概念

2.描述方法

3.算法效率

二、算法的时间复杂度

三、算法的空间复杂度

---

一、算法

1.基本概念

通俗的讲，算法是解决问题的方法，比如在现实生活中一道菜谱，一个安装轮椅的操作指南等。

严格的说，算法是对特定问题求解步骤的一种描述，是指令的有限序列。

算法具有的基本特性有：

（1）有穷性。一个算法必须总是在执行有穷步之后结束，且每一步都在有求时间内完成。

（2）确定性。算法中的每一条指令必须有确切的含义，不存在二意性。

（3）可行性。这个算法是可执行的。并且算法的每一条指令都可以被分解为基本的可执行的操作步骤。

一个“好”算法还具有正确性，健壮性，可理解性，抽象分级，高效性等特性。

2.描述方法

算法的描述方法可以将所设计算法中设计的求解步骤记录下来。常用的描述算法的方法有自然语言、流程图、程序设计语言和伪代码等。

3.算法效率

如何衡量一个算法的效率？

        每当算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度 主要衡量一个算法的运行快慢。

空间复杂度 主要衡量一个算法运行所需要的额外空间。

二、算法的时间复杂度

        撇开与计算机应硬软件有关的因素，影响算法时间代价的最主要因素是问题规模。所以运行算法所需要的时间T就是问题规模n的函数，记作 T(n)。它定量描述了该算法的运行时间。

        一 个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。

        为了客观的反映一个算法的执行时间。可以用算法中基本语句的执行次数来度量算法的工作量（基本语句是执行次数与整个算法执行次数成正比的语句）。

        只考察当问题规模充分大时。算法中基本语句的执行次数在渐进意义下的阶称作算法的渐进时间复杂度。简称为时间复杂度。

        简而言之，一个算法所花费的时间与其中基本语句的执行次数成正比例，算法中的基本操作语句的执行次数，为算法的时间复杂度。到某条基本语句与问题规模n之间的数学表达式，就算出了该算法的时间复杂度。

        但是，有时我们在计算基本语句的执行次数时，可能会发现有些次数计算时非常麻烦。所以实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么就需要使用大O的渐进表示法。

大O的渐进表示法：

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

推导大O阶方法：  

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

举例：计算时间复杂度

void Func(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

这里的问题规模是N，基本语句为++count，基本操作次数为F(N)=2N+10，那么有大O的渐进表示法就为O(n)。

常见的时间复杂度有：

三、算法的空间复杂度

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

        空间复杂度不是算程序占用了多少字节的空间，而算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似，也使用大O的渐进表示法。

算法在运行过程中所需的存储空间包括：

①输入输出数据占用的空间;②算法本身占用的空间；③执行算法需要的辅助空间。

其中，输人输出数据占用的空间取决于问题，与算法无关；算法本身占用的空间虽然与算法相关，但一般其大小是固定的。所以，算法的空间复杂度是指算法在执行过程中需要的辅助空间数量，也就是除算法本身和输人输出数据所占用的空间外,算法临时开辟的存储空间。

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

举例1：计算空间复杂度

void Bubble_sort(int arr[], int sz)
{int i = 0;for (i = 0; i < sz - 1; i++){int flag = 0;int j = 0;for (j = 0; j < sz - 1 - i; j++){//从小到大排序if (arr[j] > arr[j + 1]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;flag = 1;}}if (flag == 0){break;}}
}

这段代码中所有变量均为预先确定数量的局部变量：  int i、int flag、int j、int temp（总计4个整型变量）所以空间复杂度是O(1)。

举例2：计算空间复杂度

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)