如何提高代码效率——时间复杂度与空间复杂度—

这篇具有很好参考价值的文章主要介绍了如何提高代码效率——时间复杂度与空间复杂度——【C语言】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

当我们面对一个问题时，会有许多种解题思路。我们现在的计算机技术已经达到非常先进的地步，所以当我们用不同的方法对待问题时，时间差异不会很明显，内存差异我们一般在平常小问题时感受不到，所以我们不会去纠结程序的优化过程。

但是在以后的生活中，程序内容将会非常丰富，时间与空间的效率也就能体现出来，今天就让我们对程序的时间与空间进行学习。

算法效率

如何衡量一个算法的好坏

算法的复杂度

时间复杂度

时间复杂度的概念

大O的渐进表示法

常见时间复杂度计算举例

空间复杂度

常见空间复杂度计算举例

常见复杂度对比

算法效率

如何衡量一个算法的好坏

如何衡量一个算法的好坏呢？比如对于以下斐波那契数列：
long long Fib(int N)
{
 if(N < 3)
 return 1;

 return Fib(N-1) + Fib(N-2);
}
斐波那契数列的递归实现方式非常简洁，但简洁一定好吗？那该如何衡量其好与坏呢？

虽然代码非常简洁，但是当我们将N的取值大于50之后，想要算出结果就非常的困难，电脑会进行大量计算。

算法的复杂度

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。 时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

时间复杂度

时间复杂度的概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

即：找到某条基本语句与问题规模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;
}
printf("%d\n", count);
}

我们需要计算出++count总共执行了多少次？在for循环嵌套中++count使用了N²次，在第三个for循环中又执行了2N次，最后在while循环中M=10，所以++count循环了10次，所以++count总共执行了N²+2N+10次

如何提高代码效率——时间复杂度与空间复杂度——【C语言】,算法,数据结构

当我们在N取大值时，表达式中只有最高次数项对表达式影响大。

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

大O的渐进表示法

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

推导大O阶方法：

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

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

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

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

N = 10 F(N) = 100 N = 100 F(N) = 10000 N = 1000 F(N) = 1000000

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

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

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

平均情况：任意输入规模的期望运行次数最好情况：任意输入规模的最小运行次数(下界) 例如：在一个长度为N数组中搜索一个数据x

最好情况：1次找到最坏情况：N次找到平均情况：N/2次找到

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

常见时间复杂度计算举例

// 计算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);
}

这段程序在第一个for循环中执行了M次，在第二个for循环中执行了N次，所以用大O表示O(M+N)

// 计算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;
 }
}

求BubbleSort的时间复杂度。这个函数就是冒泡排序法，如果我们对一组数组进行排序，最好的情况是N，只需要检查一次即可。最坏的情况就是一直要进行顺序调换，需要执行(N*(N+1))/2次，通过推导大O阶方法+时间复杂度一般看最坏，时间复杂度为 O(N^2)。

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
 assert(a);
 int begin = 0;
 int end = n-1;
 // [begin, end]：begin和end是左闭右闭区间，因此有=号
 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;
}

这个函数是二分查找法，我们需要求此函数的时间复杂度。

如何提高代码效率——时间复杂度与空间复杂度——【C语言】,算法,数据结构

根据上图我们就可以得出二分查找的时间复杂度为O(logN).

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

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

我们现在已经学会了时间复杂度，我们可以算一下用递归求斐波那契数列的时间复杂度，我们就能知道为什么用递归求斐波那契数列只是代码简洁，但并不是好方法！！

如何提高代码效率——时间复杂度与空间复杂度——【C语言】,算法,数据结构

通过上图我们就可以得到这个递归的时间复杂度为O(2^N)，所以这个算法很不好！！！

空间复杂度

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

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

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

常见空间复杂度计算举例

// 计算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;
 }
}

此函数使用了常数个额外空间，开辟了size_t int、int exchange、size_t i这三个变量空间，所以空间复杂度为 O(1)。

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

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

使用递归计算斐波那契数，因为在每次调用函数时，都要开辟一块函数栈帧，当调用完成后就会对此函数的栈帧空间进行销毁，所以当我们计算空间复杂度时，我们得按着顺序进行累加计算，当函数还没有使用完成时不会去递归调用别的内容。因为斐波那契额数递归如同一个树，但是空间复杂度与时间复杂度不相同，空间复杂度是看在同一时间调用的次数，所以这个函数的空间复杂度为N，用大O表示为O(N).