这篇文章主要介绍“如何理解C语言数据结构时间复杂度及空间复杂度”，在日常操作中，相信很多人在如何理解C语言数据结构时间复杂度及空间复杂度问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”如何理解C语言数据结构时间复杂度及空间复杂度”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
一、时间复杂度和空间复杂度是什么？
1.1算法效率定义
1.2时间复杂度概念
1.3空间复杂度概念
二、如何计算常见算法的时间复杂度和空间复杂度
2.1时间复杂度计算
2.2空间复杂度计算
2.3快速推倒大O渐进表达法
三、一些特殊的情况
算法效率分为两种，一种是时间效率——时间复杂度，另一种是空间效率——空间复杂度
时间复杂度，简言之就是你写一个代码，它解决一个问题上需要走多少步骤，需要花费多长时间。打个简单的比方：现在给10个数，要求找到7在哪里1,2,3,4,5,6,7,8,9,10。我们要求写一个代码，同学狗蛋写了一个暴力查找，从第一个数依次往后遍历，他的算法要找7次，同学狗剩写了一个二分法查找，只要找2次，这就是时间复杂度的比较
算法中的基本操作的执行次数，为算法的时间复杂度
空间复杂度，是对一个算法在运行过程中临时占用存储空间大小的量度。举个栗子：我们现在要求写一个代码，狗蛋啪啪啪敲了一大堆变量，程序运行了，狗剩就用了很少的变量，程序也运行了。但是他们两个在代码运行中变量多少不同，占用的内存多少是不一样的。空间复杂度，它计算的是变量的个数。
我们在计算时间/空间复杂度时用的都是大O渐进表示法（是一种估算法）
我们以一个简单的函数举例
代码如下：
void func1(int n)
{
int i = 0;
int j = 0;
int k = 0;
int count = 0;
for (i = 0;i < n;i++)
{
for (j = 0;j < n;j++)
{
count++;
}
}
for (k = 0;k < 3 * n - 1;k++)
{
count++;
}
}试问：该函数如果被调用，要运行多少次？
我们清楚的看出i进去有n次，共有n个i，第一个for结束要运行n^ 2次，第二个for要执行3n-1次，共执行n^ 2+3n-1次
那么我们这里的时间复杂度是否就是n^2+3n-1呢？答案是否的
我们前面说过，时间复杂度和空间复杂度用的都是大O渐进表示法，是一种估算法
我们取的值，是取对表达式中影响最大的那个
我们以n^ 2+3 * n-1这个式子进行举例：设f(n)=n^2+3n-1
n=1,f(n)=1+3-1=3
n=10,f(n)=100+30-1=129
n=100,f(n)=10000+300-1=10299
n=1000,f(n)=1002999
…
很容易发现，对f(n)影响最大的是n^ 2,设g（n）=n^2
n=1,g(n)=1
n=10,g(n)=100
n=100,g(n)=10000
n=1000,g(n)=1000000
…
当n越大，g（n）就越接近f（n）
那么这里的时间复杂度大O渐进表达法写法是这样的：O(n^2)
在学习空间复杂度的求解之前，我们要知道，空间复杂度也是用大O渐进表达法进行求解，我们计算的不是所占空间大小，而是变量的个数。先来看一段代码：
代码如下（示例）：
#include<stdio.h>
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 end、int exchange、size_t i，尽管我们这个函数会经历很多的循环，但这三个变量是反复使用的，也就是说他们所占的空间是被反复使用的，空间的多少是没有变的,这里区别时间复杂度——时间是累计的，空间是不累计的（对于时间复杂度，每次循环都会被计算；对于空间复杂度，空间是可以被反复使用的）。
我们上面说过，空间复杂度计算也是用的大O渐进表示法，对于常数，我们统一用O(1)表示（大O渐进表示法详情见时间和空间复杂度篇1）
ps1:assert通常用于诊断程序中潜在的BUG，通过使用assert(condition)， 当condition为false时，程序提前结束运行，利于程序BUG的定位。
ps2:size_t是一种类型，把它看作long unsigned int
我们再来看一段代码：
代码如下（示例）：
//计算bubblesort的空间复杂度
#include<stdio.h>
long long Factorial(size_t n)
{
return N < 2 ? N : Factorial(n - 1)*n;
}这段代码是一个很简单的递归实现阶乘运算，那么它的空间复杂度是多少呢？我们先假设传过去的n=10。
10传过来我们会进行10次递归，每次递归是创建一个函数栈帧（也就是一个空间），共创建10次，每一次的空间复杂度都是O（1）。把10换成n，也就是进行n次递归，每次递归会创建1个函数栈帧，空间复杂度是O(n)。
ps：可能会有小伙伴问，那函数栈帧递归往回走的时候不是销毁了吗？注意：这里的空间复杂度是计算的“最坏、最多的情况”，况且不管是什么函数，在使用过后其栈帧都会销毁，空间复杂度算的是它用的空间最多的时候。
1.常数1代替所有加法运算中的常数
2.只保留最高阶（高数极限思想）
3.若最高阶存在且不为常数，则去除最高阶的系数，比如3*n^ 9，去掉系数变为n^9
我们再来看两个代码训练一下
代码1如下：
void func2(int n)
{
int i = 0;
int k = 0;
int count = 0;
for (i = 0;i < 3n;i++)
{
count++;
}
for (k = 0;k < 6;k++)
{
count++;
}
}这里f（n）=3n+6，它的大O渐进表达法就是O（n）
代码2如下：
void func3(int n)
{
int i = 0;
int count = 0;
for (i = 0;i < 1000;i++)
{
count++;
}
}这里一眼就看出是运行1000次，用什么来表示呢？前面说过：常数1代替所有加法运算中的常数，所以这里不管常数有多大，只要你只有一个常数都用O(1)表示
一些注意事项：
O(1)这个时间复杂度的估值是不随n的改变而改变的，以大白话说，不管你输入的n是多少，我这个算法的效率是不变的
O(n)这个时间复杂度是随n改变的
打个通俗的比方：设一个函数O(x)=1,那你x随意多少，函数值都是1
设一个函数O(X)=x，那这里函数值就随x变换而变换了
有些算法的时间复杂度是存在最好、平均、最坏情况：
最坏情况：任意输入规模的最大运行次数（上界）
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数（下界）
不多说，举例说明：
代码如下：
const char*strchr(char*str, char c)
{
while (*str != '\0')
{
if (*str == c)
{
return str;
}
++str;
}
return NULL;
}上面的代码是一个简单的查找字符的函数，比如我们现在给一串字符共n个字符“aaaaba…aaac”（省略号省略a）
这里查找a一下子就找到了，查找b要点功夫，查找c就更慢了，如果查找d，不好意思，查无此d。
那么这里就出现了最好情况：一次找到O（1）
平均情况：O（n/2）
最差情况：O（n）
对于这里最坏情况可能有同学要说为什么是O（n），你看最坏情况没找到不是吗？这里解释是这样的，你找c要n次，找d是找不到也要找n次才能确定找不到。
到此，关于“如何理解C语言数据结构时间复杂度及空间复杂度”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
