C++ 超详细分析数据结构中的时间复杂度

目录
  • 什么是时间复杂度和空间复杂度
  • 如何计算时间复杂度和空间复杂度
  • 如何计算时间复杂度和空间复杂度

别别着急划走哈,如果你跟我一样是大学生,那么你发现了一个宝藏!我们往后看-->

什么是时间复杂度和空间复杂度

要想了解时间复杂度和空间复杂度,我们得知道什么是时间复杂度和空间复杂度!

有的人看到这就明白了,而有的人却去追求它的内涵:

见名知意嘛,时间复杂度不就是表示一个算法运行完所需要的时间?这还用问?错错错!

我来举一个很简单的例子:你家隔壁老王买了一台 i9 12900k 和 RTX3080Ti 整个64GB的内存,你眼瞅着你 4G的内存,洋垃圾的处理器,打开个PS都要冒烟的那种,来来来,你跟我说说能比吗?

所以简单来说,时间复杂度主要衡量的是一个算法的运行速度,在计算机科学中,算法的时间复杂度其实是一个函数,他定量描述了该算法的运行时间。一个算法执行所耗费的时间。从理论上来说,是不能被算出来的,只有你把你的程序放在机器上跑起来才能知道,但是我们不需要每个算法都上机测试,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。

我们再来看空间复杂度-->

有了上面的案例,我们要做一个有内涵的程序猿,空间复杂度绝不是一个程序占用了多少bytes的空间!

空间复杂度是用来衡量一个算法所需的额外空间!我们早期的计算机容量很小,在那个时候对空间复杂可谓是很在乎,但是现在随着计算机的发展,现在我们都是在用空间换时间,所以我们如今已经不需要再特别关注一个算法的空间复杂度!

简单做个总结:时间复杂度算的是基本操作的执行次数,空间复杂度算的是变量的个数!

有的小伙伴看到这蛮开心,懂了。 但是不着急,我们下面来看如何计算常见的空间复杂度和时间复杂度!

如何计算时间复杂度和空间复杂度

我们直接上代码!

// 请计算一下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执行了多少次?由上面讲的可知,要我们算的就是时间复杂度!

我们可以看到第一个大for循环执行次数是N²次,第二个for循环执行次数是2*N次,下面while 循环M是等于10的,所以会执行10次,由此可见 F(N) = N² + 2 * N + 10

但是实际中我们计算时间复杂度时,我们并不需要计算准确的执行次数,只需要大概执行次数,这里我们用大O的渐进表示法。

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

推导大O阶的方法:

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中,只保留最高阶项。

3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

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

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

另外有些算法的时间复杂度存在最好、平均和最坏情况:

比如:在一个长度为N数组中搜索一个数据 x

最好情况:一次找到

最坏情况:N次找到

平均情况:N/2次找到

我们在实际中一般情况关注的是算法的最坏运行情况!,所以数组中搜索数据时间复杂度为O(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渐进表示法。

据题意我们可知,形参*a, n 函数内部创建了变量 end, i, exchange使用了5个额外空间,所以根据推导大O阶的方法可知空间复杂度为O(1)。

下面给大家总结下复杂度对比的图:

如何计算时间复杂度和空间复杂度

相信看完上边的小伙伴们已经按耐不住想要写代码了,接下来我们来看两道有复杂度要求的算法题练习题,相信你听我分析完会竖起大拇指说:妙啊!

话不多说直接上题目!!!

题目1:数组nums包含从0n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?

题目来源:面试题 17.04. 消失的数字 - 力扣(LeetCode) (leetcode-cn.com)

输入:[9,6,4,2,3,5,7,0,1]
输出:8

思路1:先排序 -> 0 1 2 3 4 5 6  8 9   然后直接遍历,判断后一个数是不是比前一个数大1,就直    接找到了!但是!时间复杂度不符合题目要求,最快的排序 O(N*logN)

思路2:把0~N的数加起来结果是ret1,再把数组中的数加起来是ret2,ret1-ret2就是我们要找的数!

思路3:异或 - 数组中的数依次跟0~N的有所数异或,最后剩下的数据就是缺的那个数字!

最后我们来实现这道题的代码:

int missingNumber(int* nums, int numsSize)
{
	int x = 0;
	//先跟数组中的值异或
	for (int i = 0; i < numsSize; ++i)
	{
		x ^= nums[i];
	}
	//再跟[0, N]之间的数异或
	for (int j = 0; j < numsSize + 1; ++j)
	{
		x ^= j;
	}
	return x;
}

看到这先别说妙,我们接着看下一道题!

题目2:给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?

输入: nums = [1,2,3,4,5,6,7], k = 3

输出: [5,6,7,1,2,3,4]

解释:

向右轮转 1 步: [7,1,2,3,4,5,6]

向右轮转 2 步: [6,7,1,2,3,4,5]

向右轮转 3 步: [5,6,7,1,2,3,4]

题目来源:189. 轮转数组 - 力扣(LeetCode) (leetcode-cn.com)

思路1: 旋转k次,先把数组nums最后一个元素放到一个临时变量tmp,然后从倒数第二个元素往后移动,再把 tmp 存的最后一个元素的值赋给数组nums[0]。缺陷:效率低,时间复杂度为O(N*K)

思路2:用空间换时间,开辟一个跟nums一样大的数组出来,先把后k个放到新数组,再把前k个接着放入新数组,时间复杂度为O(N),但是空间复杂度为O(N),不符合题意!

思路3:后k个逆置,前n-k个逆置,再整体逆置!

最后我们来实现这道题的代码:

void Revers(int* nums, int left, int right)
{
	while (left < right)
	{
		int tmp = nums[left];
		nums[left] = nums[right];
		nums[right] = tmp;
		++left;
		--right;
	}
}

void rotat(int* nums, int numsSize, int k)
{
	if (k >= numsSize)
	{
		k %= numsSize;
	}
	Revers(nums, numsSize - k, numsSize - 1);
	Revers(nums, 0, numsSize - k - 1);
	Revers(nums, 0, numsSize- 1);
}

完结撒花!!!!

动动发财的小手,留个关注留个赞,我们快乐编程不头秃。

gitee(码云):Mercury. (zzwlwp) - Gitee.com

到此这篇关于C++ 超详细分析数据结构中的时间复杂度的文章就介绍到这了,更多相关C++ 时间复杂度内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++找出字符串中出现最多的字符和次数,时间复杂度小于O(n^2)

    已知字符串"aabbbcddddeeffffghijklmnopqrst"编程找出出现最多的字符和次数,要求时间复杂度小于O(n^2) /******************************************************** Copyright (C), 2016-2017, FileName: main9 Author: woniu201 Description:求字符串中出现次数最多的字符和次数 ******************************

  • 浅谈c++性能测试工具之计算时间复杂度

    google benchmark已经为我们提供了类似的功能,而且使用相当简单. 具体的解释在后面,我们先来看几个例子,我们人为制造几个时间复杂度分别为O(n), O(logn), O(n^n)的测试用例: // 这里都是为了演示而写成的代码,没有什么实际意义 static void bench_N(benchmark::State& state) { int n = 0; for ([[maybe_unused]] auto _ : state) { for (int i = 0; i <

  • C++ 超详细分析数据结构中的时间复杂度

    别别着急划走哈,如果你跟我一样是大学生,那么你发现了一个宝藏!我们往后看--> 要想了解时间复杂度和空间复杂度,我们得知道什么是时间复杂度和空间复杂度! 有的人看到这就明白了,而有的人却去追求它的内涵: 见名知意嘛,时间复杂度不就是表示一个算法运行完所需要的时间?这还用问?错错错! 我来举一个很简单的例子:你家隔壁老王买了一台 i9 12900k 和 RTX3080Ti 整个64GB的内存,你眼瞅着你 4G的内存,洋垃圾的处理器,打开个PS都要冒烟的那种,来来来,你跟我说说能比吗? 所以简单来说

  • C++ 超详细分析数据结构中的时间复杂度

    目录 什么是时间复杂度和空间复杂度 如何计算时间复杂度和空间复杂度 如何计算时间复杂度和空间复杂度 别别着急划走哈,如果你跟我一样是大学生,那么你发现了一个宝藏!我们往后看--> 什么是时间复杂度和空间复杂度 要想了解时间复杂度和空间复杂度,我们得知道什么是时间复杂度和空间复杂度! 有的人看到这就明白了,而有的人却去追求它的内涵: 见名知意嘛,时间复杂度不就是表示一个算法运行完所需要的时间?这还用问?错错错! 我来举一个很简单的例子:你家隔壁老王买了一台 i9 12900k 和 RTX3080T

  • Java 超详细讲解数据结构中的堆的应用

    目录 一.堆的创建 1.向下调整(以小堆为例) 2.创建堆 3.创建堆的时间复杂度 二.堆的插入和删除 1.堆的插入 2.堆的删除 三.堆的应用 1.堆排序 2.top-k问题 [求最小的K个数] 四.常用接口的介绍 1.PriorityQueue的特性 2.优先级队列的构造 一.堆的创建 1.向下调整(以小堆为例) 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子) 如果parent的左孩子存在,即:child < size,

  • Java 超详细讲解数据结构中的堆的应用

    目录 一.堆的创建 1.向下调整(以小堆为例) 2.创建堆 3.创建堆的时间复杂度 二.堆的插入和删除 1.堆的插入 2.堆的删除 三.堆的应用 1.堆排序 2.top-k问题(求最小的K个数) 四.常用接口的介绍 1.PriorityQueue的特性 2.优先级队列的构造 一.堆的创建 1.向下调整(以小堆为例) 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子) 如果parent的左孩子存在,即:child < size, 进

  • C语言超详细讲解数据结构中双向带头循环链表

    目录 一.概念 二.必备工作 2.1.创建双向链表结构 2.2.初始化链表 2.3.动态申请节点 2.4.打印链表 2.5.销毁链表 三.主要功能 3.1.在pos节点前插入数据 尾插 头插 3.2.删除pos处节点数据 尾删 头删 3.3.查找数据 四.总代码 List.h 文件 List.c 文件 Test.c 文件 五.拓展 一.概念 前文我们已经学习了单向链表,并通过oj题目深入了解了带头节点的链表以及带环链表,来画张图总体回顾下: 在我们学习的链表中,其实总共有8种,都是单双向和带不带

  • C语言超详细讲解数据结构中的线性表

    目录 前言 一.分文件编写 1.分文件编写概念 2.代码展示 二.动态分布内存malloc 1.初识malloc 2.使用方法 三.创建链表并进行增删操作 1.初始化链表 2.在链表中增加数据 3.删除链表中指定位置数据 四.代码展示与运行效果 1.代码展示 2.运行效果 总结 前言 计算机专业都逃不了数据结构这门课,而这门课无疑比较难理解,所以结合我所学知识,我准备对顺序表做一个详细的解答,为了避免代码过长,采用分文件编写的形式,不仅可以让代码干净利落还能提高代码可读性,先解释部分代码的含义,

  • Redis对象与redisObject超详细分析源码层

    目录 一.对象 二.对象的类型及编码 redisObject 结构体 三.不同对象编码规则 四.redisObject结构各字段使用范例 4.1 类型检查(type字段) 4.2 多态命令的实现(encoding) 4.3 内存回收和共享对象(refcount) 4.4 对象的空转时长(lru) 五.对象在源码中的使用 5.1 字符串对象 5.1.1字符串对象创建 5.1.2 字符串对象编码 5.1.3 字符串对象解码 5.1.4 redis对象引用计数及自动清理 六.总结 以下内容是基于Red

  • C++超详细分析红黑树

    目录 红黑树 红黑树的概念 红黑树的性质 红黑树结点的定义 红黑树的插入操作 情况一 情况二 情况三 红黑树的验证 用红黑树封装map.set 红黑树的迭代器 封装map 封装set 红黑树 红黑树的概念 红黑树的概念 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black. 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的. 红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是

  • 超详细分析C语言动态内存管理问题

    目录 一.为什么存在动态内存的分配 二.动态内存函数的介绍 2.1 malloc和free 2.2 calloc 2.3 realloc 三.常见的动态内存错误 3.1 对NULL指针的解引用操作 3.2 对动态开辟空间的越界访问 3.3 对非动态开辟内存使用free释放 3.4 对同一块动态内存多次释放 3.5 动态开辟内存忘记释放(内存泄漏) 四.几个经典的笔试题 五.C/C++程序的内存开辟 六.柔性数组 6.1 柔性数组的特点 6.2 柔性数组的使用 6.3 柔性数组的优势 上期结束了[

  • Java超详细分析泛型与通配符

    目录 1.泛型 1.1泛型的用法 1.1.1泛型的概念 1.1.2泛型类 1.1.3类型推导 1.2裸类型 1.3擦除机制 1.3.1关于泛型数组 1.3.2泛型的编译与擦除 1.4泛型的上界 1.4.1泛型的上界 1.4.2特殊的泛型上界 1.4.3泛型方法 1.4.4类型推导 2.通配符 2.1通配符的概念 2.2通配符的上界 2.3通配符的下界 题外话: 泛型与通配符是Java语法中比较难懂的两个语法,学习泛型和通配符的主要目的是能够看懂源码,实际使用的不多. 1.泛型 1.1泛型的用法

随机推荐