当前位置： 首页 > article >正文

数据结构：时间复杂度与空间复杂度

article 2024/9/21 13:54:33

目录

  • 算法效率
  • 时间复杂度
    • 大O渐进表示法
    • 时间复杂度计算案例
  • 空间复杂度
    • 空间复杂度案例
  • 复杂度算法题

算法效率

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

时间复杂度

定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运行时间呢？

  1. 因为程序运行时间和编译环境和运行机器的配置都有关系，比如同⼀个算法程序，用⼀个老编译器进⾏编译和新编译器编译，在同样机器下运行时间不同。
  2. 同⼀个算法程序，用⼀个老的低配置机器和新的高配置机器，运行时间也不同。
  3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

算法的时间复杂度是⼀个函数式T(N)到底是什么呢？这个T(N)函数式计算了程序的执行次数。假设每个语句编译的时间都一样，那程序语句执行的次数就与时间成正比，用次数就可以间接反映算法的时间。
假设同一个问题，算法a程序T(N)=N,算法b程序T(N)=N^2，那算法a就优于算法b。
举个例子：

// 请计算⼀下Func1中++count语句总共执⾏了多少
次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)//外循环n次
{
for (int j = 0; j < N ; ++ j)//内循环n次
{
++count;//一共循环n*n次
}
}
for (int k = 0; k < 2 * N ; ++ k)//循环2n次
{
++count;
}
int M = 10;
while (M--)//循环10次
{
++count;
}
}

每个循环的语句都标注在程序后面，得出T(N)如下：
有的会问那些int M等语句不算吗？但是那些算上的话一共就两次，与N^2和2N比太小了，这里就直接忽略了。
T(N)=N^2+2N+10;
实际中我们计算时间复杂度时，计算的也不是程序的精确的执行次数，精确执行次数计算起来还是很麻烦的(不同的⼀句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执行次数意义也不大，因为我们计算时间复杂度只是想比较算法程序的增长量级，也就是当N不断变大时T(N)的差别，上面我们已经看到了当N不断变大时常数和低阶项对结果的影响很小，所以我们只需要计算程序能代表增长量级的大概执行次数，复杂度的表示通常使用大O的渐进表示法。

大O渐进表示法

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

  1. 时间复杂度函数式T(N)中，只保留最高阶项，去掉那些低阶项，因为当N不断变大时，低阶项对结果影响越来越小，当N无穷大时，就可以忽略不计了。
    用上面的列子来说：T(N)就可以写为N^2，后面的低阶项和常数就可以忽略了。
  2. 如果最高阶项存在且不是1，则去除这个项目的常数系数，因为当N不断变大，这个系数对结果影响越来越小，当N无穷大时，就可以忽略不计了。
    例如：2N^2 与 N^2是等价的，当N无穷大，系数2的影响可以忽略。
  3. T(N)中如果没有N相关的项⽬，只有常数项，⽤常数1取代所有加法常数。

时间复杂度计算案例

案例1：

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

T(N)=2N+10;
最高阶是2N，后面的低阶项和常数项忽略，最高阶的的系数也可以忽略；
所以这段程序的时间复杂度就是：O(N)。

案例2：

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)//循环M次
{
++count;
}
for (int k = 0; k < N ; ++k)//循环N次
{
++count;
}
printf("%d\n", count);
}

T(N)=M+N;
当M<<N时：复杂度为O(N);
当M>>N时：复杂度为O(M);
当M==N时：复杂度为O(M+N);
因为他有两个影响次数的参数，分别是M和N，复杂度算的是情况最坏的情况，也就是M和N都趋于无穷，那他们两个共同决定运行次数；
所以复杂度就是O(M+N);

案例3：

// 计算Func4的时间复杂度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)//循环100次
{
++count;
}
printf("%d\n", count);
}

T(N)=100；
由大O渐进表示法第三条可得：
时间复杂度为O(1);

案例4：
功能，在源字符串中寻找子字符串（假设字符串长度趋于无穷）

// 计算strchr的时间复杂度？
const char * strchr ( const char* str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '\0')
return NULL;
p_begin++;
}
return p_begin;
}

第一种情况：
要找的字符串在源字符串前面：Y(N)=常数；时间复杂度：O(I)；
第二种情况：
在中间位置：T(N)=N/2;时间复杂度：O(N)；
第三种情况：
在末尾：T(N)=N;时间复杂度：O(N)；
取最坏结果：时间复杂度为O(N)；

案例5：

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}

递归就相当与循环调用一个函数N次；
通过判断可知这个递归函数一共调用N次；
所以它的时间复杂度：O(N)。

空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运行过程中因为算法的需要额外临时开辟的空间。
空间复杂度不是程序占用了多少bytes的空间，因为常规情况每个对象大小差异不会很大，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
注意：函数运行时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运⾏时候申请的额外空间来确定。

空间复杂度案例

案例1：

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n//1次; end > 0; --end)
{
int exchange = 0;//2次
for (size_t i = 1//3次; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}

由分析可知在运行时创建的临时变量有三个，T(N)=3；
所以空间复杂度为O(1);

案例2：

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
if(N == 0)
return 1;
return Fac(N-1)*N;
}

在c语言学习中，函数的使用要创建栈帧空间，前面分析了这个递归要运行N次这个函数，运行一次就创建一个函数栈帧空间，所以T(N)=N；
它的空间复杂度：O(N)。

复杂度算法题

轮转N个数据：
数组元素： 0 1 2 3 4
轮转1次：4 0 1 2 3
轮转2次：3 4 0 1 2

void rotate(int* nums, int numsSize, int k) {
while(k--)
{
int end = nums[numsSize-1];
for(int i = numsSize - 1;i > 0 ;i--)
{
nums[i] = nums[i-1];
}
nums[0] = end;
}
}

外循环K次，内循环N次。
可知一共循环KN次。
最欢结果，让数据轮转N次，即T(N)=NN=N^2;
时间复杂度：O(N^2)。

现在出个问题，让它的时间复杂度降低。
思路1：刚开始提到可以用空间复杂度来分担时间复杂度。
代码实现：

void rotate(int* nums, int numsize, int k) {
int newnums[numsize];//创建大小为N的字符串
for(int i =0;i<numsize;i++)
{
newnums[i]=nums[(i+k)%numsize];
}
for(int i=0;i<numsize;i++)
{
nums[i]=newnums[i];
}

时间复杂度：T(N)=2N–> O(N);
空间复杂度：T(N)=N–>O(N)。

思路2：
在这里插入图片描述
如图数组里存放5个数，轮转2次。
先操作前半部分：交换第一个与第二个数据，如果前半部分数据较多（交换第二个跟倒数第二的数据，依次类推）
交换后数组变成：2 1 3 4 5；
然后相同的方法交换后半部分，
交换后数组：2 1 5 4 3；
然后交换整个数组，
交换后：3 4 5 1 2，
交换完成。
空间复杂度O(1),时间复杂度O(N)

void swap(int* nums,int left, int right)
{
	while (left < right)
	{
		int tmp = nums[left];
		nums[left] = nums[right];
		nums[right] = tmp;

		left++;
		right--;
	}
	
}
void rotate(int* nums, int numsize, int k) {
	
	k%= numsize;
	swap(nums, 0,k-1);
	swap(nums, k,numsize-1);
	swap(nums, 0,numsize-1);
}

这个思路不难，就是不容易想出来。它既节省了空间复杂度，还优化了时间复杂度。
----------------------------------------------分隔符
时间复杂度与空间复杂度就介绍完了，希望对各位看官有所帮助。
有错请在评论区指正，谢谢。


http://www.kler.cn/news/306588.html

相关文章：

  • 【代码随想录训练营第42期 Day57打卡 - 图论Part7 - Prim算法与Kruskal算法
  • 后端开发刷题 | 数字字符串转化成IP地址
  • 状态机按键消抖（学习笔记）
  • Flink有界流实现(1)
  • 【Python】谷歌浏览器总是自动更新，使用selenium跟chromedriver版本不匹配怎么办？
  • 01，大数据总结，zookeeper
  • 算法练习题27——疫情下的电影院（模拟）
  • AI辅助癌症诊断取得了进展
  • Angular面试题一
  • 大模型 LLM（Large Language Models）如今十分火爆，对于初入此领域的新人小白来说，应该如何入门 LLM 呢？是否有值得推荐的入门教程呢？
  • 深度学习自编码器 - 引言篇
  • java基于PDF底层内容流的解析对文本内容进行编辑
  • 象过河手机进销存，外出办公更方便，随时了解经营情况
  • C# 静态static
  • 基于HTML5的下拉刷新效果
  • 如何避免长距离遗忘问题
  • HarmonyOS NEXT 封装实现好用的网络模块（基于最新5.0的API12）
  • Android 12 Launcher3 去掉Hotseat
  • JVM 调优篇7 调优案例3- gc overhead limit exceed
  • ListBox显示最新数据、左移和右移操作
  • K8s中HPA自动扩缩容及hml
  • idea2024.2永久使用
  • MFC工控项目实例之十五定时刷新PC6325A模拟量输入
  • HTML添加文字
  • 【深度学习】Pytorch基础
  • 分享一些成功的 SQL 优化案例
  • 2024工业机器视觉产业现状
  • 多模态大语言模型综述(中)-算法实用指南
  • 如何在Django中创建新的模型实例
  • MFC工控项目实例之十六输入信号验证