算法学习—算法运行时间、logN、NlogN

2023-10-12 06:08

本文主要是介绍算法学习—算法运行时间、logN、NlogN,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1大部分程序的大部分指令之执行一次,或者最多几次。如果一个程序的所有指令都具有这样的性质,我们说这个程序的执行时间是常数。
logN 如果一个程序的运行时间是对数级的,则随着N的增大程序会渐渐慢下来,如果一个程序将一个大的问题分解成一系列更小的问题,每一步都将问题的规模缩减成几分之一,一般就会出现这样的运行时间函数。在我们所关心的范围内,可以认为运行时间小于一个大的常数。对数的基数会影响这个常数,但改变不会太大:当N=1000时,如果基数是10,logN等于3;如果基数是2,logN约等于10.当N=1 00 000,logN只是前值的两倍。当N时原来的两倍,logN只增长了一个常数因子:仅当从N增长到N平方时,logN才会增长到原来的两倍。
N如果程序的运行时间的线性的,很可能是这样的情况:对每个输入的元素都做了少量的处理。当N=1 000 000时,运行时间大概也就是这个数值;当N增长到原来的两倍时,运行时间大概也增长到原来的两倍。如果一个算法必须处理N个输入(或者产生N个输出),那么这种情况是最优的。
NlogN如果某个算法将问题分解成更小的子问题,独立地解决各个子问题,最后将结果综合起来,运行时间一般就是NlogN。我们找不到一个更好的形容,就暂且将这样的算法运行时间叫做NlogN。当N=1 000 000时,NlogN大约是20 000 000。当N增长到原来的两倍,运行时间超过原来的两倍,但超过不是太多。
N平方如果一个算法的运行时间是二次的(quadratic),那么它一般只能用于一些规模较小的问题。这样的运行时间通常存在于需要处理每一对输入数据项的算法(在程序中很可能表现为一个嵌套循环)中,当N=1000时,运行时间是1 000 000;如果N增长到原来的两倍,则运行时间将增长到原来的四倍。
 N三次方类似的,如果一个算法需要处理输入数据想的三元组(很可能表现为三重嵌套循环),其运行时间一般就是三次的,只能用于一些规模较小的问题。当N=100时,运行时间就是1 000 000;如果N增长到原来的两倍,运行时间将会增长到原来的八倍。
2的N次方如果一个算法的运行时间是指数级的(exponential),一般它很难在实践中使用,即使这样的算法通常是对问题的直接求解。当N=20时,运行时间是1 000 000;如果增长到原来的两倍时,运行时间将是原时间的平方!

log log N 可以看作是一个常数:即使N很多,两次去对数之后也会变得很小

 

这篇关于算法学习—算法运行时间、logN、NlogN的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/193807

相关文章

Java获取当前时间String类型和Date类型方式

《Java获取当前时间String类型和Date类型方式》:本文主要介绍Java获取当前时间String类型和Date类型方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录Java获取当前时间String和Date类型String类型和Date类型输出结果总结Java获取

Python实现批量提取BLF文件时间戳

《Python实现批量提取BLF文件时间戳》BLF(BinaryLoggingFormat)作为Vector公司推出的CAN总线数据记录格式,被广泛用于存储车辆通信数据,本文将使用Python轻松提取... 目录一、为什么需要批量处理 BLF 文件二、核心代码解析:从文件遍历到数据导出1. 环境准备与依赖库

MySQL多实例管理如何在一台主机上运行多个mysql

《MySQL多实例管理如何在一台主机上运行多个mysql》文章详解了在Linux主机上通过二进制方式安装MySQL多实例的步骤,涵盖端口配置、数据目录准备、初始化与启动流程,以及排错方法,适用于构建读... 目录一、什么是mysql多实例二、二进制方式安装MySQL1.获取二进制代码包2.安装基础依赖3.清

在IntelliJ IDEA中高效运行与调试Spring Boot项目的实战步骤

《在IntelliJIDEA中高效运行与调试SpringBoot项目的实战步骤》本章详解SpringBoot项目导入IntelliJIDEA的流程,教授运行与调试技巧,包括断点设置与变量查看,奠定... 目录引言:为良驹配上好鞍一、为何选择IntelliJ IDEA?二、实战:导入并运行你的第一个项目步骤1

go中的时间处理过程

《go中的时间处理过程》:本文主要介绍go中的时间处理过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 获取当前时间2 获取当前时间戳3 获取当前时间的字符串格式4 相互转化4.1 时间戳转时间字符串 (int64 > string)4.2 时间字符串转时间

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Golang如何对cron进行二次封装实现指定时间执行定时任务

《Golang如何对cron进行二次封装实现指定时间执行定时任务》:本文主要介绍Golang如何对cron进行二次封装实现指定时间执行定时任务问题,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录背景cron库下载代码示例【1】结构体定义【2】定时任务开启【3】使用示例【4】控制台输出总结背景

k8s上运行的mysql、mariadb数据库的备份记录(支持x86和arm两种架构)

《k8s上运行的mysql、mariadb数据库的备份记录(支持x86和arm两种架构)》本文记录在K8s上运行的MySQL/MariaDB备份方案,通过工具容器执行mysqldump,结合定时任务实... 目录前言一、获取需要备份的数据库的信息二、备份步骤1.准备工作(X86)1.准备工作(arm)2.手

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据