C语言数据结构(1)复杂度(大o阶)

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

欢迎来到博主的专栏——C语言与数据结构
博主ID——代码小豪

如何判断代码的好坏

实现相同作用的不同代码,如何分辨这些代码的优劣之处呢?

有人说了,我写的代码10行,别人写的是20行,我的代码更加简洁。那就是好代码

在可读性方面可能会更优(简洁≠可读性高),但是一个软件的使用者是用户啊,用户不需要能够看明白你的代码,用户需要的是软件的使用体验。

因此判断一个算法的好与劣可以用运行时间来衡量。

那么如何得到一个程序的运行时间呢?最好的方法当然是运行测试一下。但是这样做的问题也就出现了。

我用一台00年的电脑,和一台24年电脑运行一段代码,当然是24年的电脑运行更快啦,甚至有可能是24年的电脑运行坏代码比00年的电脑运行好代码更快。那么难道能说运行快的代码比较好?

这种判断的方法明显受到了硬件层面的影响,程序员应该专注于程序,在程序方面来判断算法的优劣,于是时间复杂度和空间复杂的概念就出现了。

这两个概念是用来判断实现的代码的算法的优劣性的。

时间复杂度

代码的运行时间,和算法的执行次数是明显呈现正相关关系的。

比如那个写了10行的代码,但是循环了100多次。而那个写了20行的代码,只需要执行1次。那么很明显,后者的运行时间快于前者。

时间复杂度的判断也是基于此,通过计算算法的执行次数来估计程序的运行快慢

什么是时间复杂度

时间复杂度是一个数学函数,用来评估一个算法在n的输入规模下,与执行指令的次数的关系

以计算1~n的各个数之和为例。常见的算法有以下两种

int sum_of_nums(int n)
{
	int sum = 0;
	for (int i = 1; i < n; i++)
	{
		sum += i;
	}
	return sum;
}

可以发现,当n为100时,这个算法执行的指令次数为202次

```c
int sum_of_nums(int n)
{
	int sum = 0;//1次
	for (int i = 1; i <= n; i++)//100次
	{
		sum += i;//100次
	}
	return sum;//1次
}

如果输入为n,那么这个算法执行的指令总次数为2n+2次。

高中数学学过等差数列的求和公式为

Sn=n*(a1+an)/2

而1~n的整数求和本质上也就是a1为1,an为n的等差数列求和,所以用这种算法写出来的代码如下

int sum_of_nums(int n)
{
	int sum = 0;
	sum = n * (1 + n) / 2;
	return sum;
}

这个算法无论输入N等于多少,指令的执行次数都是3次。

很明显后者的算法优于前者,并且随着n的增加,后者的优势会更加明显。

那么我们假设还有一种算法,其实现是这样的

int sum_of_nums(int n)
{
	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			if (j == i)
				sum += j;
		}
	}
	return sum;
}

如果输入为n,这个算法执行的次数为(1+2+3+……+n)+2,即n/2+n^2/2+2.

将上述算法的指令执行次数和输入规模的关系画成一个函数关系图,图形如下:
C语言数据结构(1)复杂度(大o阶),C语言数据结构,c语言,数据结构,算法
(手绘图形,不会画曲线–+)

根据图形,算法一:f(N)=2N+2是一个线性函数,因此时间复杂度是O(N),也就是常说的线性阶

算法2 f(N)=3,可以看到图像是一个常数函数,因此时间复杂度为O(1),也就是常数阶。

算法3 f(N)=N/2+N^2/2+2 可以看到图像是一个指数函数,因此时间复杂度为O(N^2),即指数阶。

时间复杂度O(f(n))是用来评定算法的快慢的,大O阶实际上是一个估值。或者说是一个算法的评级,常见的复杂度有以下几种
(1)常数阶,O(1)
(2)线性阶,O(2)
(3)对数阶,O(logN) (二分查找就是典型的O(logN)的算法)
(4)指数阶,O(N^2)

看到这有人就觉得很疑惑了,比如我写的一个算法,运行指令和输入的关系函数f(n)=n,而别人的是f(n)=2n,但是为什么时间复杂度都是O(N)呢,明明我的程序更好啊,我不服。

实际上时间复杂度可以认为是一个算法的评级,比如考英语四级,我考了424,而别人考了100,虽然我的英语水平肯定高于100,但是英语的评级我们两个都是没过四级。

当然了,这种优化还是不错的,虽然没有将O(N)变成O(1),但是在运行速度当然会更快一步。

如何计算时间复杂度

时间复杂度的计算方式在上面就已经可以明显感觉到了。

即时间复杂度取决于输入与执行指令的关系函数的最高次数项。
比如f(N)=2N^2+22+3,那么这个算法的时间复杂度就是O(N^2),实际上也是很好理解的,如下图
C语言数据结构(1)复杂度(大o阶),C语言数据结构,c语言,数据结构,算法
对比可以发现,当n超过一定数量的时候, 只有次数高的项对指令的运行次数影响最大,其余项可以忽略不计。

计算大O阶的方法总结
(1)只保留最高次数项
(2)保留的最高次数项将系数改为1
(3)如果只有常数项,那么就是1.

空间复杂度

算法中除了运行的指令外,还有用来存储数据的内存空间也是需要考虑在内的,但是现代的计算机对于空间的需求已经不再那么抠抠索索了,甚至大部分的算法采取的思路都是“以空间换取时间”。

比如判断1~10000的水仙花数,除了使用大量的指令让其计算以外,也可以创造一个10000元素大小的数组,将已知的水仙花数对应下标的元素记为1,这样子就从计算水仙花数的问题,变为了检索数组元素的问题,时间缩减,但是空间上要多出10000个元素的空间占用。

空间复杂度的计算公式为S(n)=O(f(n)),f(n)为执行指令时,对内存占用空间的函数,比如递归的空间复杂度就是O(n),因为每次执行递归,都会在内存中多开辟一个空间。文章来源地址https://www.toymoban.com/news/detail-806021.html

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

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

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

相关文章

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

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

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

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

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

    目录 1、算法效率 1如何衡量一个算法的好坏 2算法的复杂度 2、时间复杂度 1时间复杂度的概念 2大O的渐进表示法 2时间复杂度计算例题 1、计算Func2的时间复杂度 2、计算Func3的时间复杂度 3、计算Func4的时间复杂度 4、计算strchr的时间复杂度 5、计算BubbleSort的时间复杂度 6、计算

    2024年02月03日
    浏览(68)
  • c语言版:数据结构(时间复杂度,空间复杂度,练习)

        时间复杂度是用来衡量算法执行时间的一个指标。它表示随着输入规模的增加,算法执行时间的增长率。时间复杂度通常用大O符号表示。    在计算时间复杂度时,通常会 忽略常数项、低阶项和系数项 , 只关注随着输入规模增长而导致的主要影响。这是因为在实际应用

    2024年01月21日
    浏览(51)
  • 学习数据结构:算法的时间复杂度和空间复杂度

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

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

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

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

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

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

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

    2023年04月24日
    浏览(67)
  • 从头开始:数据结构和算法入门(时间复杂度、空间复杂度)

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

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

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

    2024年02月12日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包