<数据结构>NO1.算法的时空复杂度

这篇具有很好参考价值的文章主要介绍了<数据结构>NO1.算法的时空复杂度。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

<数据结构>NO1.算法的时空复杂度

🚩算法效率

算法是一个被设计好的,计算机可实施的有限步骤或次序,包含一系列清晰的指令。
一个算法需要在有限的时间和空间内被执行,衡量算法效率高低就是通过执行算法所需要的时间和空间

算法复杂度

算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏,一般是从<font color = >时间空间两个维度来衡量的,即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。


🪅时间复杂度

时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是在不同的环境下,执行的速度又有差异,因此有了时间复杂度这个分析方式一个算法所花费的时间与其中所有语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。
更加通用的时间复杂度表示方法为[ 大O符号表示法 ],即T(n)=O(f(n)),f(n)表示每行代码的执行次数之和,大O表示正比关系。这个公式的全称为:算法的渐进时间复杂度

常见的时间复杂度有

  • O(1)
  • O(logn)
  • O(n)
  • O(nlogn)
  • O(n2)
  • O(n3)
  • O(2^n)
  • O(n!)

这里举个例子来讲解如何计算时间复杂度的大O表示法

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

F(N)=N2+2*N+10

  • N=10 ----------- F(N)=130
  • N=100 ----------F(N)=10210
  • N=1000---------F(N)=1002010

当N越来越大时,2*N和10对F(N)的影响可以忽略,所以F(N)的值主要由N2来决定,所以该算法的大O表示法为O(n2)

大O的渐进表示法

大O符号(Big O notation):是用于描述函数渐进行为的数学符号

  1. 用常数1去掉运行时间的所有加法常数
  2. 在修改后的运行次数函数中,只保留最高项
  3. 使最高项的系数为1,得到大O表示法

对于存在最好、最坏、平均的时间复杂度算法
最坏情况:任意输入规模的最大运行次数
最好情况:任意输入规模的最小运行次数
平均情况:任意输入规模的期望运行次数
例如:在一个长度为N数组中搜索一个数据x
最好情况:1次搜索到x
最坏情况:搜索N次仍然没有找到x
平均情况:搜索2/N次
在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

常见的时间复杂度举例

示例一

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);
}

时间复杂度O(n):基本循环语句执行次数为2n+10,忽略常数项和最高项系数就是n

示例二

void Func3(int N, int M)
{

	int count = 0;
	++count;
	int count = 0;
	for (int k = 0; k < M; ++k)
	{
		++count;
	}
	for (int k = 0; k < N; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

时间复杂度为O(m+n),基本循环语句执行次数为m+n

示例三

void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

时间复杂度为O(1):循环体执行的次数为100,是一个常数,所以时间复杂度为O(1)

示例四

// 计算strchr的时间复杂度?
const char * strchr ( const char * str, int character )

时间复杂度为O(n2):strchr函数是在字符串中寻找某一个字符第一次出现的位置,所以时间复杂度最好的情况是O(1),最坏的情况是O(n2),时间复杂度取决于最坏情况

示例五

// 计算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(n2):考虑最坏情况,数组从大到小排序,这样总共的循环次数就是(n-1)+(n-2)+……+(0),也就是(n2-1)/2,所以时间复杂度为O(n2)

示例六

// 计算BinarySearch的时间复杂度?
int BinarySearch(int* a, int n, int x)
{
 assert(a);
 int begin = 0;
 int end = n-1;
 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;
}

时间复杂度为O(log2n):由二分查找的定义可以直到,二分查找每次执行循环体一次,目标区间会缩小一半,最坏情况下查找的元素为两边的端点,所以在最坏情况下一定有等式n/2k=1(k为循环体执行次数),所以k=log2n

示例七

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

时间复杂度为O(n):递归也是循环的一种,当n为0时,递归结束,所以循环体一共执行n次<数据结构>NO1.算法的时空复杂度

示例八

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

时间复杂度为O(1.6n):<数据结构>NO1.算法的时空复杂度
<数据结构>NO1.算法的时空复杂度
在上述例子中,如果将红色框部分补齐的话那么上述总共会调用20+21+…+2n-2次函数,这样算出来的时间复杂度就是O(2n),所以说时间复杂度的一个上限是O(2n),但这绝对不是最小上限,最小上限为O(((1+sqrt(5))/2)n)大约是O(1.6n)
感兴趣的朋友可以看这篇文章递归求斐波那契数列的时间复杂度


🪅空间复杂度

大O的渐进表示法

考虑算法的效率除了要考虑算法的时间效率,还需要考虑到算法的空间效率,和时间复杂度一样,我们无法直接知道每一台机器上一个算法具体消耗的内存有多少kb,所以我们也使用[ 大O符号表示法 ]表示一个算法的空间效率,S(n)=O(f(n)),f(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;
 }
}

空间复杂度为O(1):在程序运行时,每一次循环只会开辟一个额外的空间exchange,所以空间复杂度为O(1)

示例二

// 计算Fibonacci的空间复杂度?
// 返回斐波那契数列的前n项
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;
}

空间复杂度为O(n):动态内存分配是在程序运行时才进行内存分配,所以产生的数组空间是程序运送时额外开辟的,所以空间复杂度为O(n)

示例三

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

空间复杂度为O(n):<数据结构>NO1.算法的时空复杂度
每一个参数不为0的函数都会调用一个函数,所以最开始的参数为n的话,运行时会调用n次递归函数,会额外开辟n个函数栈帧,所以空间复杂度为O(n)

示例四

//计算fib递归函数的空间复杂度
int fib(int n)
{
	if (n < 3)
		return 1;
	else
		return fib(n - 1) + fib(n - 2);
}

空间复杂度O(n):在此之前我们来回顾一下栈区的特性-----栈区空间的使用习惯是先使用高地址,后使用低地址,栈区中存放的是局部变量、函数栈帧。当函数调用结束后或者变量生命周期结束后、该区域会归还给线程。以便下次调用
先思考下面代码
<数据结构>NO1.算法的时空复杂度
为什么两个函数中开辟变量的地址是一样的?

由栈区使用习惯可知:当fun1函数会建立一个函数栈帧,变量a是在该栈帧中创建的,fun1函数结束时、会销毁函数栈帧,原本fun1所占用的空间归还给进程以便再次利用该空间,那什么时候需要再次利用该空间呢?答案是当fun2函数调用的时候会利用和函数fun1开辟的相同的栈帧,原因在于fun2的结构和fun1的结构是一模一样的,尽管变量名和数据不一样,但是从内存的角度来看只需要知道这两函数都是初始化了一个int的变量和执行了printf函数语句,本质上没有区别,所以当两个函数的栈帧是一样的,既然栈帧一样,那么两个函数也一定是在同一个为自豪定义变量的

现在回到最开始的问题,为什么递归的斐波那契空间复杂度是O(n)?
来看下面这张图
<数据结构>NO1.算法的时空复杂度
调用fib函数时,会先调用最左边的fib(n-1),fib(n-2)…fib(3)…fib(2),此时额外开辟的栈桢数是n-1,当执行完fib(2)后,fib(2)的空间会被回收,fib(2)返回是为了计算fib(3),所以当fib(2)返回后回调用fib(1),由之前分析可知fib(1)的空间是fib(2)销毁的栈帧空间,所以此时额外开辟的空间仍然是n-1,计算fib(4)时fib(2)分配的空间是fib(3)销毁的空间,计算fib(5)时fib(3)分配的空间是fib(4)销毁的空间,计算fib(3)时又会为fib(2)\fib(1)开辟空间,fib(1)的空间就是fib(2)销毁的空间,以此类推,最后额外开辟的空间最多就是n-1个函数栈帧,所以空间复杂度为O(n)


🗯️常见复杂度对比🗯️

5201314 O(1) 常数阶
3n+4 O(n) 线性阶
3n2+4n+5 O(n2) 平方阶
3log2n+4 O(log2n 对数阶
2n+3nlog2n+14 O(nlog2n) nlog2n阶
n3+2n2+4 O(n3) 立方阶
2n O(2n) 指数阶

<数据结构>NO1.算法的时空复杂度文章来源地址https://www.toymoban.com/news/detail-415806.html

到了这里,关于<数据结构>NO1.算法的时空复杂度的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构和算法】时间复杂度和空间复杂度

    目录   一、前言 二、时间复杂度 2.1时间复杂度表示形式 2.1.1规则: 3.1如何计算时间复杂度 3.1.1线性阶 3.1.2平方阶 3.1.3对数阶 常见的时间复杂度排序: 三、空间复杂度 3.1Java的基本类型内存占用 数据结构和算法是程序的灵魂,这是某位程序员大佬所言,学习了这门,我们便可

    2023年04月09日
    浏览(44)
  • 数据结构与算法—时间复杂度和空间复杂度

    目录 1、什么是数据结构? 2、什么是算法? 3、算法的复杂度 4、时间复杂度 (1) 时间复杂度的概念:  (2) 大O的渐进表示法:  六个例题: (3) 时间复杂度对比:  三个例题:  OJ题分析时间复杂度 5、空间复杂度 (1)常见复杂度对比  (2)OJ题分析空间复杂度 小结 数据结构 (D

    2024年02月07日
    浏览(86)
  • 数据结构--算法的时间复杂度和空间复杂度

    算法效率是指 算法在计算机上运行时所消耗的时间和资源 。这是衡量算法执行速度和资源利用情况的重要指标。 例子: 这是一个斐波那契函数,用的是递归的计算方法,每次创建函数就会在栈区开辟一块空间,递归次数越多,开辟空间越多; 所以, 代码的简洁说明不了算

    2024年02月15日
    浏览(43)
  • 数据结构与算法-时间复杂度与空间复杂度

    数据结构是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。 算法就是定义良好的计算过程,他取一个或一组的值为输入,并产生一个或一组值作为输出。简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果。 算法在

    2024年02月07日
    浏览(47)
  • 算法的复杂度【数据结构】

    算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源,因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的,即 时间复杂度 和 空间复杂度 时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。 方法

    2024年02月08日
    浏览(38)
  • 【数据结构】算法的复杂度

    大家好!今天我们来学习算法的复杂度。 目录 1. 前言 1.1 什么是数据结构? 1.2 什么是算法? 2. 算法效率 3. 时间复杂度 3.1 时间复杂度的概念 3.2 大O的渐进表示法 3.3 常见时间复杂度计算举例 ​4. 空间复杂度 4.1 空间复杂度的概念 4.2 常见空间复杂度计算举例 5. 常见复杂度

    2024年02月11日
    浏览(38)
  • 【数据结构与算法】1.时间复杂度和空间复杂度

    📚博客主页:爱敲代码的小杨. ✨专栏:《Java SE语法》 ❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️ 🙏小杨水平有限,欢迎各位大佬指点,相互学习进步! 算法效率分为两种:第一种是时间效率;第二种是空间效率。时间效率又称为时间

    2024年01月20日
    浏览(49)
  • 【数据结构与算法篇】时间复杂度与空间复杂度

       目录 一、数据结构和算法 1.什么是数据结构?  2.什么是算法? 3.数据结构和算法的重要性 二、算法的时间复杂度和空间复杂度 1.算法效率 2.算法的复杂度 3.复杂度在校招中的考察 4.时间复杂度 5.空间复杂度  6.常见复杂度对比 7.复杂度的OJ练习   👻内容专栏:《数据结

    2023年04月24日
    浏览(60)
  • 学习数据结构:算法的时间复杂度和空间复杂度

    衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。 时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。 算法的时间复杂度 算法中的基本操作的执行次数,为算法的时间复杂度。 算法的

    2024年04月11日
    浏览(40)
  • 数据结构 | 算法的时间复杂度和空间复杂度【详解】

    数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。 算法(Algorithm):就是定义良好的计算过程,他取一个或一组的值为输入,并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤,用来将输入数据转

    2024年02月08日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包