复杂度(上卷)

前言

在正式进入今天的主题之前,我们不妨先来回顾一下初步学习数据结构后必须知道的概念。🎶

数据结构

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

(没有一种单一的数据结构能够满足所有用途,因此我们需要学习各种不同的数据结构。如:线性表、树、图、哈希等。)

算法

算法(Algorithm)指的是定义好的计算过程,它取一个或一组的值为输入,并产生出一个或一组值作为输出

简单来说算法就是一系列的计算步骤,用于将输入数据转化成输出结果。


正文

我们知道算法有好坏之分,但是要怎么去衡量一个算法的好坏呢?

比如我们在一些刷题平台做算法题时会遇到“超出时间限制”的“滑铁卢”,所以我们可以知道,时间就是其中一个标准。除此之外还有空间。用最少的时间办最大的事是我们现实中办事能力好坏的标准,对于算法来说也是类似的:用最少的时间、最少的空间,解决问题,这就是好的算法。

其实我们有一个专门衡量算法好坏的概念:复杂度。复杂度分为时间复杂度和空间复杂度,刚好从两个维度去衡量一个算法。

说得更精确一些:时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间

其实在计算机发展的早期,计算机的存储容量很小所以对空间复杂度很是在乎。而如今计算机的存储容量不可同日而语,所以我们已不再特别关注空间复杂度而是以时间复杂度为主

小小补充:摩尔定律

摩尔定律最初是由英特尔公司的创始人之一戈登·摩尔在1965年提出的观察结果和预测。他发现集成电路上可容纳的晶体管数量每隔一段时间就会翻倍,同时价格也会减半。这一发现揭示了信息技术进步的速度,并成为了计算机行业的基础法则之一。

摩尔定律的实际效果是,计算机芯片的性能每隔一段时间就会显著提高,而成本也会随之下降。这一定律对整个信息技术产业的发展产生了深远的影响,推动了半导体芯片的集成化趋势,进而给人们的生活带来了巨大的变化。然而,随着晶体管电路逐渐接近性能极限,摩尔定律的适用性也面临挑战。

归纳起来,“摩尔定律”主要有以下3种“版本”:

  1. 集成电路芯片上所集成的电路的数目,每隔18个月就翻一番;
  2. 微处理器的性能每隔18个月提高一倍,而价格下降一半;
  3. 用一美元所能买到的计算机性能,每隔18个月翻两番。

这里不再多阐述,回到复杂度。

时间复杂度

在计算机科学中,算法的时间复杂度是一个函数式T(N),它定量描述了该算法的运行时间。

这里的函数不是我们C语言中指的函数,而是数学概念。

先来说说,时间复杂度是衡量程序的时间效率,那么为什么不去计算程序的运行时间呢?

我们是可以计算程序的运行时间的。我们可以分别计算程序开始和结束的时间进行相减得到运行时间。

如:

#include<stdio.h>
#include<time.h>

int main()
{
	//计算程序运行时间
	int begin = clock();//用来保存程序的运行时间
	int count = 0;
	for (int i = 0; i < 1000000000; i++)
	{
		count++;
	}
	int end = clock();
	printf("time:%d\n", end - begin);
	return 0;
}

执行后我的电脑上VS(Debug模式)得到的结果是time:507,Release模式则是0。单位是毫秒。

而且多次运行得出来的结果还不一定相同,无法给出精确的运行时间。

  1. 程序运行时间和编译环境以及运行机器的配置都有关系,同一个算法程序,用一个老编译器和新编译器进行编译,在同样机器下运行时间不同。

  2. 同一个算法程序,用一个老低配置机器和新高配置机器,运行时间也不同。

  3. 并且运行的时间只能程序写好后测试,不能在编写程序之前通过理论思想计算评估。(而我们希望算法的复杂度是我们在编写程序之前就能知道的。)

这几点解释了为什么通过计算程序的运行时间来评估算法的时间效率不好。

时间复杂度和空间复杂度是我们在提出一个算法,编写程序之前就能知道的,是一个粗估而非精确的结果。

时间复杂度该怎么计算呢?

程序的时间效率由两个维度决定:每条语句运行的时间和运行的次数。

程序时间效率:每条语句运行时间×运行次数

每条语句运行的时间也如前面所说,和编译环境、运行机器的配置等有关,不好确定。但是运行的次数我们是可以知道的。比如上面的int count = 0;这句代码的运行次数为1,而count++;的运行次数为1000000000。

我们可以将每条语句运行时间去掉,只看运行次数。

为什么可以这样呢?

在这里插入图片描述

因为程序的运行时间和运行次数是正相关的,所以我们可以不看每条语句运行时间,通过运行次数来看时间复杂度。

计算时间复杂度的案例

我们现在有一道算法题,来看看怎么计算它的时间复杂度。

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

我们看的是运行次数。在第一个嵌套循环中:外循环每执行1次,内循环要执行N次,而外循环执行了N次。所以整个部分执行了N×N次;在下一个循环中执行了2×N次;最后一个循环执行了10次。所以该算法的时间复杂度函数式为T(N)=N²+2N+10。

定义变量这样的语句相较于其他的循环语句运行次数太小,故忽略不计。

我们可以看出N的大小决定了T(N)的大小:

NT(N)
10130100
1001021010000
100010020101000000

可以看出对T(N)影响大的是N²,而2N+10对结果的影响小,可以忽略不计,只看影响最大的项。T(N)=N²,是一个粗估。

大O的渐进表示法

上面我们讲了T(N),但其实复杂度的表示我们使用的是大O的渐进表示法。

比如上面的那个算法的时间复杂度就表示为O(N²)。

大O既可以表示时间复杂度,也可以表示空间复杂度。

接下来我们来看本文中最重要的内容:

推导大O阶规则

  1. 时间复杂度函数式T(N)中,只保留最⾼阶项,去掉那些低阶项,因为当N不断变⼤时, 低阶项对结果影响越来越⼩,当N⽆穷⼤时,就可以忽略不计了。
  2. 如果最⾼阶项存在且不是1,则去除这个项⽬的常数系数,因为当N不断变⼤,这个系数 对结果影响越来越⼩,当N⽆穷⼤时,就可以忽略不计了。
  3. T(N)中如果没有N相关的项⽬,只有常数项,⽤常数1取代所有加法常数。

可以看到,刚才那个算法的例子就是符合以上规则的一个例子。

我们现在再来看几个例子。

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

第一个循环执行次数为2N,第二个循环次数为10。所以T(N)=2N+10

根据规则1,10作为低阶项,被去掉;

根据规则2,最⾼阶项存在且不是1,去除这个项⽬的系数2。

所以最后我们得到的时间复杂度为O(N)。

对于计算机来说,1万和2万,1亿和2亿的区别并不大,所以可以去除系数。2倍的无穷大与无穷大结果一样。

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

第一个循环的执行次数为M,第二个循环执行次数为N,所以T(N)=M+N,M和N都是变量,都会影响T(N)的大小。那么时间复杂度是多少呢?答案是O(M+N)。

如果T(N)=2M+N,也是O(M+N),没有区别。因为M和N取极限时,2倍的极限和极限没有区别。

大小关系复杂度
M>>NO(M)
M<<NO(N)
M==NO(M+N)

注意:

  • 这里的高阶项与低阶项如何区别?高和低是相对而言的,看谁对结果影响最大则为高阶。

  • 一亿这样的数对于我们来说虽然感觉很大,对于高速处理数据的计算机来说却不过是一秒不到的事,所以我们说数字大与小是要对于计算机来说而不是我们的主观感受。当我们说“非常大”,指的是无限。

本文到此结束,但对于复杂度的探讨并没有结束,敬请期待下卷。( ̄︶ ̄)↗

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

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

相关文章

如何保证RocketMQ消息不丢失

rocket mq在生产阶段、Brocker存储阶段、消费阶段都会出现消息丢失。 1、生产者防止丢失消息。 a.同步阻塞的方式发送消息&#xff0c;加上失败重试机制&#xff0c;可能broker存储失败&#xff0c;可以通过查询确认 b.异步发送需要重写回调方法&#xff0c;检查发送结果 c…

人脸表情识别Facial Expression Recognition基于Python3和Keras2(TensorFlow后端)

人脸表情识别项目是一个结合了计算机视觉和深度学习技术的高级应用&#xff0c;主要用于分析和理解人类面部表情所传达的情感状态。这样的系统可以用于多种场景&#xff0c;比如情绪分析、用户交互、市场调研、医疗诊断以及人机接口等领域。 一个典型的人脸表情识别项目可以分…

kafka与zookeeper的SSL认证教程

作者 乐维社区&#xff08;forum.lwops.cn&#xff09;许远 在构建现代的分布式系统时&#xff0c;确保数据传输的安全性至关重要。Apache Kafka 和 Zookeeper 作为流行的分布式消息队列和协调服务&#xff0c;提供了SSL&#xff08;Secure Sockets Layer&#xff09;认证机制&…

红酒与威士忌:跨界碰撞的味觉火花

在品酒的世界里&#xff0c;红酒与威士忌&#xff0c;两者如同两位优雅的舞者&#xff0c;各自在舞台上闪耀着不同的光芒。然而&#xff0c;当它们相遇&#xff0c;那跨界碰撞的味觉火花&#xff0c;却仿佛一场不可预测的华丽盛宴&#xff0c;让人为之倾倒。 一、红酒的浪漫与威…

测试狗:“微观结构表征+理论计算”助力《Science》论文发表

特大喜讯&#xff1a;祝贺四川大学王玉忠院士&#xff0c;赵海波教授&#xff0c;马健文硕士研究生&#xff08;第一作者&#xff09;在《Science》上发表新的研究成果&#xff0c;测试狗和计算狗分别提供了SEM、Micro-CT、FTIR和理论计算支持&#xff0c;供相关领域的科研工作…

【经典面试题】环形链表

1.环形链表oj 2. oj解法 利用快慢指针&#xff1a; /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode; bool hasCycle(struct ListNode *head) {ListNode* slow head, *fast…

centos9中mysql指令提示解决方案

CentOS 9 中没有 MySQL 的官方插件&#xff0c;因为 MySQL 不是 CentOS 的默认数据库&#xff0c;它是 MariaDB 的一部分。 如果想要一个命令行提示的 MySQL 客户端&#xff0c;可以使用第三方工具 &#xff0c;如mycli 首先&#xff0c;确保已经安装了 MySQL&#xff0c;且操…

【C语言】C语言-身份证管理系统(源码+注释)【独一无二】

&#x1f449;博__主&#x1f448;&#xff1a;米码收割机 &#x1f449;技__能&#x1f448;&#xff1a;C/Python语言 &#x1f449;公众号&#x1f448;&#xff1a;测试开发自动化【获取源码商业合作】 &#x1f449;荣__誉&#x1f448;&#xff1a;阿里云博客专家博主、5…

Java链表LinkedList经典题目

一.LinkedList的方法 首先先看一下链表的方法&#xff1a; 方法解释boolean add(E e)尾插void add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection c)尾插 c 中的元素E remove(int index)删除 index 位置元素boolean remove(Object o)删除遇到的第一…

【7.10更新】Win11 23H2 正式版:22631.3880镜像下载!

微软向Win11 23H2用户推送了七月最新更新补丁KB5040442&#xff0c;系统更新后&#xff0c;版本号将升至22631.3880。本次更新包括了一些安全质量更新&#xff0c;并修复了6月可选更新导致的任务栏无法加载、交互问题&#xff0c;建议大家更新。该版本系统离线制作而成&#xf…

Spring MVC入门2

Postman的使用 接上期我们抛出了一个问题&#xff0c;Postman的使用 可以点击链接下载 https://www.postman.com/downloads/ 安装之后会提示版本升级&#xff0c;直接点击dissmiss即可。 要想发送数据&#xff0c;具体歩奏如下简图&#xff1a; 还有一个更具体的图&#xff…

回归树模型

目录 一、回归树模型vs决策树模型&#xff1a;二、回归树模型的叶结点&#xff1a;三、如何决定每个非叶结点上的特征类型&#xff1a; 本文只介绍回归树模型与决策树模型的区别。如需了解完整的理论&#xff0c;请看链接&#xff1a;决策树模型笔记 一、回归树模型vs决策树模…

jpg图片怎么转成png格式?学会这四种方法,轻松完成图片转换!

jpg图片怎么转成png格式&#xff1f;在数字图像的广袤天地中&#xff0c;JPG与PNG两大格式如同两位各具魅力的艺术家&#xff0c;各自以其独特的风格赢得了人们的喜爱&#xff0c;JPG擅长运用有损压缩的技法&#xff0c;以牺牲部分图像细节为代价&#xff0c;打造出更小巧、更易…

卤味江湖中,周黑鸭究竟该抓住什么赛点?

近年来&#xff0c;卤味江湖的决斗从未停止。 随着休闲卤味、佐餐卤味等细分赛道逐渐形成&#xff0c;“卤味三巨头”&#xff08;周黑鸭、绝味食品、煌上煌&#xff09;的牌桌上有了更多新对手&#xff0c;赛道变挤了&#xff0c;“周黑鸭们”也到了转型关键期。 这个夏天&a…

tableau范围-线图与倾斜图绘制 - 14

范围-线图与倾斜图 1.范围-线图1.1 含义1.2 范围-线图1.2.1 折线图绘制1.2.2 设置计算字段1.2.3 添加详细信息1.2.4 添加参考线1.2.5 结果 2. 倾斜图2.1 含义2.2 倾斜图绘制2.2.1 数据导入2.2.2 创建计算字段2.2.3 排名编辑表计算2.2.4 显示标签2.2.5 标签格式设置2.2.6 修改排…

4.感知机

感知机 ​ 给定输入 x x x&#xff0c;权重 w w w&#xff0c;和偏移 b b b,感知机输出&#xff1a; KaTeX parse error: Unknown column alignment: o at position 16: \begin{array} o̲ \sigma(<w,x>… 或者是二分类&#xff1a;-1或1 Expected node of symbol gro…

【异常】JDK21报错NoSuchFieldError: Class com.sun.tools.javac.tree.JCTree$JCImport does not have member fie

【异常】JDK21报错NoSuchFieldError: Class com.sun.tools.javac.tree.JCTree$JCImport does not have member fie java: java.lang.NoSuchFieldError: Class com.sun.tools.javac.tree.JCTree$JCImport does not have member field com.sun.tools.javac.tree.JCTree qualid …

鸿蒙开发:Universal Keystore Kit(密钥管理服务)【HMAC(C/C++)】

HMAC(C/C) HMAC是密钥相关的哈希运算消息认证码&#xff08;Hash-based Message Authentication Code&#xff09;&#xff0c;是一种基于Hash函数和密钥进行消息认证的方法。 在CMake脚本中链接相关动态库 target_link_libraries(entry PUBLIC libhuks_ndk.z.so)开发步骤 生…

Windows netstat命令详解,Windows查看网络连接

「作者简介」&#xff1a;冬奥会网络安全中国代表队&#xff0c;CSDN Top100&#xff0c;就职奇安信多年&#xff0c;以实战工作为基础著作 《网络安全自学教程》&#xff0c;适合基础薄弱的同学系统化的学习网络安全&#xff0c;用最短的时间掌握最核心的技术。 netstat 常用来…

某客户管理系统Oracle RAC节点异常重启问题详细分析记录

一、故障概述 某日10:58分左右客户管理系统数据库节点1所有实例异常重启&#xff0c;重启后业务恢复正常。经过分析发现&#xff0c;此次实例异常重启的是数据库节点1。 二、故障原因分析 1、数据库日志分析 从节点1的数据库日志来看&#xff0c;10:58:49的时候数据库进程开始…