时间复杂度和空间复杂度计算（数据结构C语言实现1）
写在前面
数据结构C语言系列，和博主一起学习简单的数据结构和算法，都是利用C语言实现，很基础，相信大家都能够学会，都有所收获。记得点赞，收获。@TOC
本节目标
- 1.什么是时间复杂度和空间复杂度？
- 2.如何计算常见算法的时间复杂度和空间复杂度？
- 3.有复杂度要求的算法题练习
基本概念
1.什么是时间复杂度和空间复杂度？
1.1算法效率算法效率分析分为两种：
- 第一种是时间效率
- 第二种是空间效率
时间效率被称为时间复杂度，而空间效率被称作空间复杂度。
时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
1.2 时间复杂度的概念时间复杂度的定义：
在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，
算法中的基本操作的执行次数，为算法的时间复杂度。
1.3 空间复杂度的概念：
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以
空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
总结
时间复杂度并不是算法运行的时间，而是算法中基本操作（循环等）执行的次数;
因为相同的程序，在不同的机器上运行的时间不同，不同硬件比效率就是耍流氓。
空间复杂度计算的也不是计算程序占用多少个byte空间，而是计算程序变量的个数。
1.4 复杂度计算在算法的意义
出现在一些笔试题目里
像很多算法题，不仅要我们实现算法的功能，还要对复杂度有一定的要求，不然通过不了。也通常出现在一些公司的笔试题中。
工作对算法的优化
当我们进入公司工作时，但老板说优化一下算法时，要知道如何优化，将时间复杂度和空间复杂度控制到最小。
所以时间复杂度和空间复杂度的学习也是十分重要的
常见算法的时间复杂度计算
请计算Func1执行次数?
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i) //循环 N次
{
for (int j = 0; j < N ; ++ j) //循环 N次
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k) //循环 2N次
{
++count;
}
int M = 10;
while (M--) //循环 M次
{
++count;
}
printf("%d\n", count);
}
我们已经知道，算法的时间复杂度，就是程序基本操作的执行次数(循环的次数)，这便是求复杂度的题目。
我们先来计算这个算法实际循环的次数： N*N+2N+M
计算过程：
一开始两层for循环嵌套次数为N*N,然后一层for循环2N,最后一层while循环执行了M次，M=10,所以执行次数为 N*N+2N+10。
所以这个算法的时间复杂度为N*N+2N+10？
N=10 Func1(10)=10*10+2*10+10=130
N=100 Func1(100)=100*100+2*100+10=10210
N=1000 Func1(1000)=1002010
可以看到当N越来越大时，2N+10对结果的影响并不大，所以我们能否省略？
实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。
大O符号（Big O notation）：
是用于描述函数渐进行为的数学符号。
推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。
利用上面的规则得到的结果就是大O阶。
使用大O的渐进Func1的时间复杂度为：O(N^2)
利用第2点，就得到了结果O(N^2)
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况：
- 最坏情况：任意输入规模的最大运行次数(上界)
- 平均情况：任意输入规模的期望运行次数
- 最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)
2.3常见时间复杂度计算举例
有了上面的学习，我们已经知道了时间复杂度如何计算，接下来我们一起了解一下几种常见的时间复杂度计算。
实例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表示法规则1，保留最高阶数：2N
规则3，省略最高阶数常数：N
所以Func2时间复杂度为：O(N)
实例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",count）;
}
实际次数：N+M
时间复杂度：O(N+M)
如果题目特别强调
1，N远大于M 或者2，N和M相差不大
时间复杂度为O(N)
实例3
// 计算Func4的时间复杂度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}
实际次数：100
利用规则1，不管N取多少，该算法的执行次数不变，都为10次，常数同一用O(1)
时间复杂度：O(1)
实例4
// 计算strchr的时间复杂度？
const char * strchr ( const char * str, char character )
{
while(*str != '\0')
{
if(*str == character)
return str;
++str;
}
return NULL;
}
这是一个字符查找的程序，所以情况不同，执行次数不同，而大O表示法，计算的是最坏情况，
时间复杂度：O(N)
实例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;
}
}
这是个冒泡算法，我们要知道该程序的执行过程，才能够计算出该程序的时间复杂度。
第一趟冒泡
第二趟冒泡，只要到倒数第二个元素，
…
所以执行次数为
N
N-1
N-2
…
1
等比数列：(N+1）*N/2
时间复杂度：O(N^2)
实例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);
if (a[mid] < x)
begin = mid+1;
else if (a[mid] > x)
end = mid;
else
return mid;
}
return -1;
}
二分查找：又叫折半查找，过程如下：
就如同折纸
第一次 N/2 ,第二次N/2/2，…假设次数为x, 2^x=N ,所以x=log2^N
大O表示法，一般把2省略，
即时间复杂度：O(logN)
实例7
// 计算阶乘递归Factorial的时间复杂度？
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}
递归计算N的阶层，N!=1* 2 * 3.....*N
可以看到N=4递归了4次
时间复杂度：O(N)
时间复杂度对比
可以看到O(1)和O(logN)最小，然后是O(N)
可能你会疑惑，为啥O(logN)的时间复杂度这么小？
列如：如果我们用二分查找，在中国14亿人中，假如有序，你想找的某个人，需要多少次呢？
2^10=1024
2^20=100万
2^30=10亿
可以看到10亿只需要查找10次，所以14亿也就查找31次。
O(logN)的效率可想而知!
常见空间复杂度计算
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以
空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法
时间复杂度和空间复杂度区别就是时间复杂度可以累加，空间不可以累加。
就是时间用了就是用了，不能回去，而空间用了，还能销毁，下次继续用！
实例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;
}
}
上面代码，包括形参，一共创建了5个变量，所以空间复杂度为:O(1)
实例2：
/ 计算Fibonacci的空间复杂度？
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 ;
}
上面代码，malloc了n+1个空间，所以空间复杂度：O(n)
实例3：
// 计算阶乘递归Factorial的空间复杂度？
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}
递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N）
有复杂度的算法练习题
相信你们都学会了，那就来刷个题吧！
3.1消失的数字OJ链接：https://leetcode-cn.com/problems/missing-number-lcci/
3.2 旋转数组OJ链接：https://leetcode-cn.com/problems/rotate-array/
习题答案，会在另一篇博客附上！
大佬点个赞吧，加油!
持续更新…
- 点赞
- 收藏
- 关注作者
评论（0）