数据结构与算法-时间复杂度与空间复杂度

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

🎈1.概论

🔭1.1什么是数据结构?

数据结构是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。

🔭1.2什么是算法?

算法就是定义良好的计算过程,他取一个或一组的值为输入,并产生一个或一组值作为输出。简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果。

🎈2.算法效率

🔭2.1如何衡量一个算法的好坏?

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

🔭2.2算法的复杂度

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

🔭2.3时间复杂度

📖2.3.1时间复杂度的概念

时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。
即:找到某条基本语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度。

✅这里给出示例:

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

数据结构与算法-时间复杂度与空间复杂度,初阶数据结构与算法,算法,数据结构

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

实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法

📖2.3.2大O的渐进表达式

大O符号(Big O notation):是用于描述函数渐进行为的数学符号。
推导大O阶方法:

  • 用常数1取代运行时间中的所有加法常数。
  • 在修改后的运行次数函数中,只保留最高阶项。
  • 如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

使用大O的渐进表示法以后,Func1的时间复杂度为:O(N2)

  • N = 10 F(N) = 100
  • N = 100 F(N) = 10000
  • N = 1000 F(N) = 1000000

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。

📖2.3.3常见时间复杂度计算举例

✅示例二:

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

使用大O的渐进表示法以后,Func2的时间复杂度为:O(N)

✅示例三:

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

使用大O的渐进表示法以后,Func3的时间复杂度为:O(M+N)

✅示例四:

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

使用大O的渐进表示法以后,Func4的时间复杂度为:O(1)

✅示例五:

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

本函数是用来在一个字符串中找出某个字符的,那么假设我们这里的字符串是hello world
如果我们需要查找的是h,那么我们只需要查找1次,这也称为最好情况,即任意输入规模的最小运行次数。
如果我们需要查找的是w,那么我们只需要查找N/2次,这也称为平均情况,即任意输入规模的期望运行次数。
如果我们需要查找的是d,那么我们只需要查找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的渐进表示法以后,Func6的时间复杂度为:O(N2)

✅示例七:

// 计算BinarySearch的时间复杂度?
int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	// [begin, end]:begin和end是左闭右闭区间,因此有=号
	while (begin <= end)
	{
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid - 1;
		else
			return mid;
	}
	return -1;
}

使用大O的渐进表示法以后,Func7的时间复杂度为:O(logN)

✅示例八:

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

使用大O的渐进表示法以后,Func8的时间复杂度为:O(2N)

✅示例九:

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

使用大O的渐进表示法以后,Func9的时间复杂度为:O(N)

🔭2.4空间复杂度

空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少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;
	}
}

使用大O的渐进表示法以后,示例1的空间复杂度为:O(1)

✅示例2:

// 计算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的渐进表示法以后,示例2的空间复杂度为:O(N)

✅示例3:

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

使用大O的渐进表示法以后,示例3的空间复杂度为:O(N)
数据结构与算法-时间复杂度与空间复杂度,初阶数据结构与算法,算法,数据结构
✅示例4:

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

使用大O的渐进表示法以后,示例4的空间复杂度为:O(N)

空间是可以重复利用的,不累计的;时间是一去不复返的,累计的。

🔭2.5常见复杂度对比

执行次数函数 非正式术语
3 O(1) 常数阶
2n+1 O(n) 线性阶
3n2+2n+1 O(n2) 平方阶
3log2n(2为底数)+2 O(logn) 对数阶
n+4nlog2n(2为底数)+7 O(nlogn) nlogn阶
5n3+3n2+2n+1 O(n3) 立方阶
2n O(2n) 指数阶

常用时间复杂度所消耗时间从小到大依次是:O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)

数据结构与算法-时间复杂度与空间复杂度,初阶数据结构与算法,算法,数据结构

好啦,关于复杂度的知识点到这里就结束啦,后期会继续更新数据结构与算法的相关知识,欢迎大家持续关注、点赞和评论!❤️❤️❤️文章来源地址https://www.toymoban.com/news/detail-731785.html

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

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

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

相关文章

  • 数据结构--算法的时间复杂度和空间复杂度

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

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

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

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

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

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

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

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

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

    2024年04月11日
    浏览(40)
  • 【数据结构与算法篇】之时间复杂度与空间复杂度

    ❤️博客主页: 小镇敲码人 🍏 欢迎关注:👍点赞 👂🏽留言 😍收藏 🌞友友们暑假快乐,好久不见呀!!!💖💖💖 🍉 有人曾经问过我这样一个问题,“人终其一身,执着追求的东西究竟是什么?”我是这样回答的,”我们终其一生都在寻找着那个和我们灵魂极其契合

    2024年02月12日
    浏览(48)
  • 【数据结构初阶】算法的时间复杂度和空间复杂度

    1.1 如何衡量一个算法的好坏 如何衡量一个算法的好坏呢? 比如对于以下斐波那契数列: 斐波那契数列的递归实现方式非常简洁,但简洁一定好吗?那该如何衡量其好与坏呢? 1.2 算法的复杂度 算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此

    2024年02月08日
    浏览(69)
  • 从头开始:数据结构和算法入门(时间复杂度、空间复杂度)

        目录 文章目录 前言 1.算法效率 1.1 如何衡量一个算法的好坏 1.2 算法的复杂度 2.时间复杂度  2.1 时间复杂度的概念 2.2 大O的渐进表示法 2.3常见时间复杂度计算 3.空间复杂度 4.常见复杂度对比 总结 前言         C语言的学习篇已经结束,今天开启新的篇章——数据结构

    2024年02月14日
    浏览(49)
  • 算法之时间复杂度---数据结构

    目录 前言: 1.时间复杂度 1.1时间复杂度的理解 1.2规模与基本操作执行次数 1.3大O渐进表示法 1.4计算基本操作的次数 2.常见的时间复杂度及其优劣比较 ❤博主CSDN:啊苏要学习     ▶专栏分类:数据结构◀   学习数据结构是一件有趣的事情,希望读者能在我的博文切实感受到

    2024年02月05日
    浏览(65)
  • 数据结构——算法的时间复杂度

    🌇个人主页:_麦麦_ 📚今日名言: 生命中曾经有过的所有灿烂,都终究需要用寂寞来偿还。 ——《百年孤独》 目录 一、前言 二、正文         1.算法效率                 1.1如何衡量一个算法的好坏                 1.2算法的复杂度         2. 时间复杂度      

    2024年02月03日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包