时间复杂度和空间复杂度（全解）——数据结构
时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很小。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。由此可见随着N次数的增大，表达式中N^2对结果的影响最大，而时间复杂度
目录
1--时间复杂度和空间复杂度计算
【本节目标】
1.什么是时间复杂度和空间复杂度？
2.如何计算常见算法的时间复杂度和空间复杂度？
3.有复杂度要求的算法题练习
1.什么是时间复杂度和空间复杂度？
1.1算法效率
算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
1.2 时间复杂度的概念
时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。使用大O渐进表示法。
1.3 空间复杂度的概念
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
1.4 复杂度计算在算法的意义
2.1如何计算常见算法的时间复杂度？
2.2 大O的渐进表示法
// 请计算一下Func1基本操作执行了多少次？
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)
}上面func1最准确的次数是N*N+2*N+10
随着N次数的增大：
Func1 执行的基本操作次数 ：
N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010
由此可见随着N次数的增大，表达式中N^2对结果的影响最大，而时间复杂度是一个估算看表达中，影响最大的那一项。\
所以func1的时间复杂度为O（N^2）
实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后，Func1的时间复杂度为：
N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000
通过上面我们会发现大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);
}准确的次数为2*N+10
随着次数的增大，2*N对结果的影响最大
根据大O的渐进表示法的3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。
所以实例1的时间复杂度为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\n", count);
}准确的次数为M+N，那么时间复杂度为O(M+N) (时间复杂度可以为多个变量)
假设：
M远大于N，时间复杂度为 O(M)
M与N差不多大，时间复杂度为 O(N) 或 O(M)
实例3：
// 计算Func4的时间复杂度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count; }
printf("%d\n", count);
}准确的次数为100，随着N增大，次数不会变化都为100
根据大O的渐进表示法的1、用常数1取代运行时间中的所有加法常数。
所以时间复杂度为O(1).
实例4:
// 计算strchr的时间复杂度？
const char * strchr ( const char * str, char character )
{
while(*str != '\0')
{
if(*str == character)
return str;
++str; }
return NULL;
}该函数的意思是在字符串str中寻找字符character，找到后返回字符串的对应索引及下标
假设字符串长度为N
如果字符串为“sajdkfbaskjhlfbguilfm”
|
字符为s |
为最好的情况O(1) |
|
字符为b |
为平均的情况O(N/2) |
|
字符为m |
为最坏的去情况O(N) |
随着字符串的变长，最O(1)不会变，O(N)变长。
根据大O的渐进表示法中
另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)例如：在一个长度为N数组中搜索一个数据x最好情况：1次找到
最坏情况：N次找到平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)
所以实例4中时间复杂度为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^2
又根据大O渐进表示法中
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
所以实例5的时间复杂度为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;
}函数实现的功能为使用二分法来寻找x（前提是数组为有序数组）
根据以上经验，计算时间复杂度要根据算法的最坏情况，所以实例6的时间复杂度为O(logN).
实例7：
// 计算阶乘递归Factorial的时间复杂度？
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}函数使用三目运算符实现阶乘运算，下面为递归的过程，先建立函数栈桢，到达最后一个后函数回溯，并清除栈帧空间。
实例答案及分析：
1. 实例1基本操作执行了2N+10次，通过推导大O阶方法知道，时间复杂度为 O(N)
2. 实例2基本操作执行了M+N次，有两个未知数M和N，时间复杂度为 O(N+M)
3. 实例3基本操作执行了10次，通过推导大O阶方法，时间复杂度为 O(1)
4. 实例4基本操作执行最好1次，最坏N次，时间复杂度一般看最坏，时间复杂度为 O(N)
5. 实例5基本操作执行最好N次，最坏执行了(N*(N+1)/2次，通过推导大O阶方法+时间复杂度
一般看最坏，时间复杂度为 O(N^2)
6. 实例6基本操作执行最好1次，最坏O(logN)次，时间复杂度为 O(logN) ps：logN在算法分析
中表示是底数为2，对数为N。有些地方会写成lgN。（建议通过折纸查找的方式讲解logN是
怎么计算出来的）
7. 实例7通过计算分析发现基本操作递归了N次，时间复杂度为O(N)。
复杂度对比：
可能认为时间复杂度O(N)和O(logN),会差不多？
但由图可以看出，O(logN)和O(1)差不多。
可以和二分寻找法来验证也可以举例子
那么用二分查找中国14亿人口，最多查找多少次？
31次
2.2.常见空间复杂度的计算
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
空间复杂度也是使用大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; }
}根据函数可以看出，创建空间的个数为常数个，所以空间复杂度为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));
//创建空间个数为（n+1）
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：
// 计算阶乘递归Factorial的空间复杂度？
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}
空间复杂度也是，根据最坏的情况也就是使用最多空间时的空间复杂度，该函数在回溯时才会对函数创建栈帧的空间销毁，所以空间复杂度为O（N）。
实例答案及分析：
1. 实例1使用了常数个额外空间，所以空间复杂度为 O(1)
2. 实例2动态开辟了N个空间，空间复杂度为 O(N)
3. 实例3递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)
3.有复杂度要求的算法题练习
3.1消失的数字
OJ链接：https://leetcode-cn.com/problems/missing-number-lcci/
异或不用考虑对应，最后只要异或到一起就可以。因为异或有交换律。
思路一：
int missingNumber(int* nums, int numsSize) {
for(int i = 0; i < numsSize; i++)
{
int flag = 0;
for(int j = 0; j < numsSize - 1 - i; j++)
{
if(nums[j] > nums[j+1])
{
int tem;
tem = nums[j];
nums[j] = nums[j+1];
nums[j+1] = tem;
flag =1;
}
}
if(flag == 0)
{
break;
}
}
for(int i = 0; i < numsSize; i++)
{
if(nums[i] + 1 != nums[i+1])
{
return nums[i] + 1;
}
}
return -1;
}思路二：
int missingNumber(int* nums, int numsSize)
{
int ret1 = 0;
for(int i = 0; i < numsSize; i++)
{
ret1 += nums[i];
}
int ret2 = 0;
for(int i = 0; i < numsSize + 1; i++)
{
ret2 += i;
}
return ret2 - ret1;
}思路三：
int missingNumber(int* nums, int numsSize)
{
int ret1 = 0;
for(int i = 0; i < numsSize; i++)
{
ret1 ^= nums[i];
}
for(int i = 0; i < numsSize + 1; i++)
{
ret1 ^= i;
}
return ret1;
}3.2 旋转数组
OJ链接：https://leetcode-cn.com/problems/rotate-array/
思路一旋转K次
跑不过因为测试用例给了有一个大数组。
void rotate(int* nums, int numsSize, int k)
{
while(k--)
{
int temp = nums[numsSize-1];
for(int i = numsSize-2; i >=0; i--)
{
nums[i+1] = nums[i];
}
nums[0] = temp;
}
}思路二以空间换时间
void rotate(int* nums, int numsSize, int k)
{
//创建一个数组，复制一份给它
int num[numsSize];
for(int i = 0; i < numsSize; i++)
{
num[i] = nums[i];
}
int j = 0;
if(k >= numsSize)
{
k %= numsSize;
}
for(int i = 0; i < numsSize; i++)
{
//将数组后面需要逆置的赋值到前面
if(i < k)
{
nums[i] = num[numsSize - k + i];
continue;
}
//赋值不需要逆置的部分
nums[i] = num[j];
j++;
}
}思路三：
思路三：
void Reverse(int* nums, int left, int right)
{
while(left < right)
{
int tmp;
tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left ++;
right --;
}
}
void rotate(int* nums, int numsSize, int k)
{
if(k >= numsSize)
{
k %= numsSize;
}
Reverse(nums, numsSize-k, numsSize-1);
Reverse(nums, 0, numsSize-1-k);
Reverse(nums, 0, numsSize-1);
}
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
34
0- 0
已为社区贡献1条内容
所有评论(0)