C语言学习第二十六天(算法的时间复杂度和空间复杂度)

1、算法效率

衡量一个算法的好坏,是从时间和空间两个方面来衡量的,换句话说就是从时间复杂度和空间复杂度来衡量的

这里需要补充一点:时间复杂度是衡量一个算法的运行快慢,空间复杂度是主要衡量一个算法运行所需要的额外空间

2、时间复杂度

概念:算法的事件复杂度是一个函数,它定量的描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上是不能算出来的,所以出现了时间复杂度。一个算法所花费的时间与其中的执行次数成正比例。即:算法中的基本操作的执行次数,为算法的时间复杂度。

请看下面的代码:

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

在实际计算时间复杂度的时候,不一定要精确计算出执行次数,我们只需要找到其中主导时间复杂度的式子​​​​​​​,这里需要使用大O的渐进表示法

大O的渐进表示法:

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

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

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

所以上面的Func1函数的时间复杂度是O(N^2)

还有一种情况是需要注意的:当有些算法在不同的情况之下执行的次数不同,我们取得是其最坏的情况,比如这个算法的执行次数可以是1  \frac{N}{2}  N,我们取其最坏的情况,所以时间复杂度是O(N)。

下面举一些计算时间复杂度的例子,以供大家参考

例1:

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

首先进入第一个for循环,可见这个for循环要执行2N次,然后在进入下面的while循环,执行10次,一共就是10+2N次,根据上面说的时间复杂度计算方法,为O(N)。

例2:

// 计算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(N+M)。

例3:

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

这个中间的for循环被执行了100次,由上述规则,可知其时间复杂度是O(1)

例4:

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

这个是求冒泡排序的时间复杂度,我们需要找到最坏的情况,在这个最坏的情况这个算法的执行次数,为n+(n-1)+...+1=\frac{(n+1)*n}{2} ,根据上面的时间复杂度的计算方式,为O(N^{2})。

例5:

// 计算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(log n)。

例6:

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

 return Fac(N-1)*N;
}

这个例子中,递归了N次,所以其时间复杂度是O(N)

例7:

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

 return Fib(N-1) + Fib(N-2);
}

这个例子递归了N^{2}次,所以时间复杂度是O(N^{2}).

3、空间复杂度

解释:这是对一个算法在运行过程中临时占用存储空间大小的量度

需要注意的是:空间复杂度是计算的变量的个数,这个计算方法也是使用的大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)。

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

这个开辟了N个空间,所以空间复杂度是O(N),

例3:

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

 return Fac(N-1)*N;
}

递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/254345.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

「Verilog学习笔记」交通灯

专栏前言 本专栏的内容主要是记录本人学习Verilog过程中的一些知识点&#xff0c;刷题网站用的是牛客网 timescale 1ns/1nsmodule triffic_light(input rst_n, //异位复位信号&#xff0c;低电平有效input clk, //时钟信号input pass_request,output wire[7:0]clock,output reg…

Shared Worker的快速理解与简单应用

SharedWorker 是 HTML5 中引入的一种 WebWorkers 类型&#xff0c;用于在浏览器中创建可在多个浏览器窗口或标签页之间共享的后台线程。Web Workers 是在主线程之外运行的脚本&#xff0c;允许执行一些耗时的任务而不会阻塞用户界面。 对 SharedWorker 的概念、理解和应用的简要…

2023第十七届中国品牌节,酷开科技荣获金谱奖!

11月18日&#xff0c;以“复苏与腾飞”为主题的2023第十七届中国品牌节&#xff0c;在杭州市云栖小镇国际会展中心盛大开幕。来自政界、商界、文化界等领域的6000余名嘉宾出席本次盛会&#xff0c;共同见证了民族品牌的崛起&#xff0c;全力奉献一场史无前例的“品牌人的亚运会…

Pikachu漏洞练习平台之暴力破解(基于burpsuite)

从来没有哪个时代的黑客像今天一样热衷于猜解密码 ---奥斯特洛夫斯基 Burte Force&#xff08;暴力破解&#xff09;概述 “暴力破解”是一攻击具手段&#xff0c;在web攻击中&#xff0c;一般会使用这种手段对应用系统的认证信息进行获取。 其过程就是使用大量的认证信息在认…

【操作系统】实验名称: 实验五 文件系统

实验目的&#xff1a; 1. 掌握文件系统的基本概念和工作机制 2. 掌握文件系统的主要数据结构的实现 3、掌握软件系统实现算法 实验内容&#xff1a; 设计并实现一个虚拟的一级&#xff08;单用户&#xff09;文件系统程序 提供以下操作 1、文件创建/删除接口命令 2、目录创建/删…

合并 K 个排序链表——Java解答

题目&#xff1a;合并 K 个排序链表 题目描述&#xff1a; 给你一个链表数组&#xff0c;每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中&#xff0c;返回合并后的链表。 示例&#xff1a; 假设有以下三个链表&#xff1a; 1->4->5, 1->3->4,…

QUIC在零信任解决方案的落地实践

一 前言 ZTNA为以“网络为中心”的传统企业体系架构向以“身份为中心”的新型企业安全体系架构转变&#xff0c;提供解决方案。随着传统网络边界不断弱化&#xff0c;企业SaaS规模化日益增多&#xff0c;给终端安全访问接入创造了多元化的空间。其中BYOD办公方式尤为突出&#…

SpringBoot使用@DS配置 多数据源 【mybatisplus druid datasource mysql】

项目最近需要使用多数据源&#xff0c;不同的mapper分别读取不同的链接&#xff0c;本项目使用了mybatisplus druid 来配置多数据源&#xff0c;基于mysql数据库。 目录 1.引入依赖 ​2.配置文件 application.yaml 3.Mapper中使用DS切换数据源 4.使用DS的注意事项 1.引入依…

苹果忽略iPhone?2024可穿戴产品或成重心!

一代版本一代神&#xff0c;即便是强如iPhone也有着被忽视的一天&#xff0c;当然&#xff0c;这么说有些夸张。虽然iPhone永远都是苹果最重要的产品&#xff0c;但在明年&#xff0c;苹果的重心将偏向其他产品。 彭博社记者马克古曼&#xff08;Mark Gurman&#xff09;在新一…

如何确保对称密钥管理的存储安全?

确保对称密钥管理的存储安全是保障信息安全的重要一环。以下是一些建议&#xff0c;以确保对称密钥管理的存储安全&#xff1a; 使用安全存储设备&#xff1a;选择使用经过验证的安全存储设备来存储对称密钥。这些设备通常具有高度的物理安全性&#xff0c;可以防止未经授权的访…

使用Umi搭建React项目

环境准备 一、首先确保有 node环境&#xff0c;并确保 node 版本是 14 或以上。&#xff08;推荐用 nvm 来管理 node 版本&#xff0c;windows 下推荐用 nvm-windows&#xff09; nvm使用教程 二、然后需要包管理工具。node 默认包含 npm&#xff0c;但也可以选择其他方案&a…

eclipse-安装WindowBuilder,怎么安装

WindowBuilder是Eclipse的一个插件&#xff0c;可以帮助开发者使用Java Swing、JavaFX和SWT快速构建图形用户界面&#xff08;GUI&#xff09;。下面是WindowBuilder的安装步骤&#xff1a; 1. 打开Eclipse IDE&#xff08;请确保已安装JDK&#xff09;。 2. 点击“Help”菜单…

【MySQL】:表的删除和修改

表的删除和修改 一.update(修改)二.delete(删除)1.删除数据2.截断表 三.插入查询的数据四.聚合函数五.group by 句子的使用1.导入表2.进行操作 一.update(修改) 对查询到的结果进行列值更新 下面有一个表&#xff0c;接下来的操作都是对该表进行操作。 1.将孙悟空同学的数学成绩…

目标跟踪 MOT数据集和可视化

目录 MOT15数据集格式简介 gt可视化 本人修改的GT可视化代码&#xff1a; MOT15数据集格式简介 以下内容转自&#xff1a;【目标跟踪】MOT数据集GroundTruth可视化-腾讯云开发者社区-腾讯云 MOT15数据集下载&#xff1a;https://pan.baidu.com/s/1foGrBXvsanW8BI4eybqfWg?…

100GPTS计划-AI写诗PoetofAges

地址 https://chat.openai.com/g/g-Cd5daC0s5-poet-of-ages https://poe.com/PoetofAges 测试 创作一首春天诗歌 创作一首夏天诗歌 创作一首秋天诗歌 创作一首冬天诗歌 微调 诗歌风格 语气&#xff1a;古典 知识库

嵌入式Linux开发板硬件学习-基于cadence

嵌入式Linux开发板硬件学习-基于cadence 目录原理图网表输出功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants 创建一个自定义列表如何创…

本章主要介绍Spring Framework中用来处理URI的多种方式

1.使用 UriComponentsBuilder 构建URi 话不多说 直接上代码 UriComponents uriComponents UriComponentsBuilder.fromUriString("https://example.com/hotels/{hotel}").queryParam("q", "{q}").encode().build();URI uri uriComponents.exp…

js传递json数据过大的解决方案

protobufjs 使用protobuf&#xff0c;定义如下结构 Person.protobuf syntax "proto3";message Person {string name 1;int32 age 2; }Person.thrift namespace java com.example.Personstruct Person {1: required string name,2: required i32 age }使用bench…

Android笔记(十八):面向Compose组件结合Retrofit2和Rxjava3实现网络访问

一、Retrofit2 Square公司推出的Retrofit2库&#xff08;https://square.github.io/retrofit/&#xff09;&#xff0c;改变了网络访问的方式。它实现了网络请求的封装。Retrofit库采用回调处理方式&#xff0c;使得通过接口提交请求和相应的参数的配置&#xff0c;就可以获得…

3 - Electron BrowserWindow对象 关于窗口

优雅的打开应用~ 当加载缓慢&#xff0c;打开应用的一瞬间会出现白屏&#xff0c;以下方法可以解决 const mainWindow new BrowserWindow({ show: false }) mainWindow.once(ready-to-show, () > {mainWindow.show() }) 设置背景颜色 const win new BrowserWindow({ b…
最新文章