时间复杂度o(1), o(n), o(logn), o(nlogn)的理解

当我们分析算法的时间复杂度时,我们通常关注的是算法执行所需的时间与输入规模的增长之间的关系。这里我会简要介绍常见的时间复杂度:O(1)、O(n)、O(log n) 和 O(n log n),并进行对比。

O(1) - 常数时间复杂度:

表示算法的执行时间不受输入规模的影响,无论输入数据有多大,执行时间都是固定的。
示例:哈希算法等。
例子:哈希算法是典型的O(1)时间复杂度,无论数据规模多大,都可以在一次计算后找到目标(不考虑冲突的话)等。

O(n) - 线性时间复杂度:

表示算法的执行时间与输入规模成正比,随着输入规模的增加,执行时间线性增长(数据量增大几倍,耗时也增大几倍)。
示例:遍历算法等。
例子:冒泡排序,就是典型的O(n^2)的算法,对n个数排序,需要扫描n×n次。

O(log n) - 对数时间复杂度:

表示算法的执行时间与输入规模的对数成正比,随着输入规模的增加,执行时间增长缓慢(这里的log是以2为底的,比如,当数据增大256倍时,耗时只增大8倍,是比线性还要低的时间复杂度)。
示例:二分搜索等分治算法。
例子:二分查找是O(logn)的算法,每找一次排除一半的可能,256个数据中查找只要找8次就可以找到目标。。

O(n log n) - 线性对数时间复杂度:

表示算法的执行时间与输入规模和输入规模的对数之间成正比,随着输入规模的增加,执行时间增长较快(n乘以logn,当数据增大256倍时,耗时增大256*8=2048倍。这个复杂度高于线性低于平方)。
示例:快速排序、归并排序等分治算法。
例子:对数组进行快速排序、对链表进行归并排序等。

对比:

O(1) 是最快的,因为它的执行时间不受输入规模的影响。
O(log n) 在增长速度上比 O(n) 慢,而 O(n) 又比 O(n log n) 慢,因此它们之间的排序是 O(1) < O(log n) < O(n) < O(n log n)。

在实际应用中,O(1) 和 O(log n) 的算法通常被视为高效算法,而 O(n) 和 O(n log n) 的算法可能在大规模数据上表现不佳

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

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

相关文章

17.Blender RC大佬EEVEE皮肤节点预设导入

如何添加节点预设 在底下的左下角打开Geometry Node Editor 选中正方体&#xff0c;点击新建 当鼠标指针在两个模块之间&#xff0c;是十字的样子时 可以拖出一个新的板块 然后打开文件浏览器 找到节点预设然后拖入到底下的节点编辑界面就可以了或者是blend文件&#xf…

Go Web 开发 Demo【用户登录、注册、验证】

前言 这篇文章主要是学习怎么用 Go 语言&#xff08;Gin&#xff09;开发Web程序&#xff0c;前端太弱了&#xff0c;得好好补补课&#xff0c;完了再来更新。 1、环境准备 新建项目&#xff0c;生成 go.mod 文件&#xff1a; 出现报错&#xff1a;go: modules disabled by G…

vue cli 自定义项目架子,vue自定义项目架子,超详细

脚手架Vue CLI基本介绍&#xff1a; Vue CLI 是Vue官方提供的一个全局命令工具 可以帮助我们快速创建一个开发Vue项目的标准化基础架子【集成了webpack配置】 脚手架优点&#xff1a; 开箱即用&#xff0c;零配置内置babel等工具标准化的webpack配置 脚手架 VueCLI相关命令…

一种由RSOA和PIC集成的宽可调激光器

----翻译自Nouman Zia, Samu-Pekka Ojanen, Jukka Viheriala, Eero Koivusalo, Joonas Hilska, Heidi Tuorila, and Mircea Guina在optics letter上发的文章vol.48, Issue 5, pp. 1319-1322(2023) 摘要&#xff1a;通过光子集成方式实现的2-3μm波长的可调激光器&#xff0c;在…

如何选择最佳的机器学习分类模型?基于使用贝叶斯和异步连续减半算法(ASHA)优化的最佳分类模型自动选择方法

目录 一、主要内容&#xff1a; 二、贝叶斯优化算法&#xff1a; 三、异步连续减半优化算法&#xff1a; 四、代码运行效果&#xff1a; 五、代码下载&#xff1a; 一、主要内容&#xff1a; 对于分类问题&#xff0c;不同机器学习模型分类的效果不同&#xff0c;而且在同…

Azure AKS日志查询KQL表达式

背景需求 Azure&#xff08;Global&#xff09; AKS集群中&#xff0c;需要查询部署服务的历史日志&#xff0c;例如&#xff1a;我部署了服务A&#xff0c;但服务A的上一个版本Pod已经被杀掉由于版本的更新迭代&#xff0c;而我在命令行中只能看到当前版本的pod日志&#xff…

2024年最新 CKA 导航页

1. Dokcer 基础相关 Docker 、 Docker-Compose 安装教程Docker基础知识、相关概念以及基本使用命令Docker 一句话删除所有镜像/容器 2. CKA 相关学习 CKA&#xff08;Certified Kubernetes Administrator&#xff09;是由 Cloud Native Computing Foundation&#xff08;CNC…

c#实现音乐的“vip播放功能”

文章目录 前言1. c#窗体2. 功能3. 具体实现3.1 添加文件3.2 音乐播放3.3 其他功能 4. 整体代码和窗口5. 依赖的第三方库 前言 最近在QQ音乐里重温周杰伦的歌&#xff0c;觉得好听到耳朵怀孕&#xff0c;兴起想要下载下来反复听&#xff0c;发现QQ音乐VIP歌曲下载下来的格式居然…

C++初阶之list的使用和模拟以及反向迭代器的模拟实现

个人主页&#xff1a;点我进入主页 专栏分类&#xff1a;C语言初阶 C语言进阶 数据结构初阶 Linux C初阶 算法 欢迎大家点赞&#xff0c;评论&#xff0c;收藏。 一起努力&#xff0c;一起奔赴大厂 一.list简介 list是一个带头双向链表&#xff0c;在数据结构的时候…

44 网络基础

本章重点 了解网络发展背景&#xff0c;对局域网/广域网的概念有基本认识 了解网络协议的意义&#xff0c;重点理解TCP/IP五层结构模型 学习网络传输的基本流程&#xff0c;理解封装和分用 目录 1.网络发展 2.协议 3.OSI七层模型 4.TCP/IP五层模型 5.网络传输流程图 6.网络中…

VMP 简单源码分析(.net)

虚拟机 获取CPU的型号 实现了一个指令集解释器&#xff0c;每个操作码对应一个特定的处理函数&#xff0c;用于执行相应的指令操作。在执行字节码时&#xff0c;解释器会根据操作码查找并调用相应的处理函数来执行指令。 截获异常 先由虚拟机处理 处理不了再抛出异常 priva…

开源投票系统源码及搭建 在线投票活动创建系统的设计与开发

在当今数字化时代&#xff0c;在线投票活动已成为各类组织、企业和个人不可或缺的一部分。无论是选举、问卷调查、产品评选还是其他需要收集公众意见的场景&#xff0c;一个高效、稳定且易于使用的在线投票系统都至关重要。 分享一款基于开源投票系统源码的在线投票活动创建系…

设计模式Java实现-建造者模式

楔子 小七在2019年的时候&#xff0c;就想写一个关于设计模式的专栏&#xff0c;但是最终却半途而废了。粗略一想&#xff0c;如果做完一件事要100分钟&#xff0c;小七用3分钟热情做的事&#xff0c;最少也能完成10件事情了。所以这一次&#xff0c;一定要把他做完&#xff0…

ICode国际青少年编程竞赛- Python-1级训练场-综合训练1

ICode国际青少年编程竞赛- Python-1级训练场-综合训练1 1、 Spaceship.turnLeft() for i in range(2):Spaceship.turnLeft()Spaceship.step(3) Dev.step(-1) Spaceship.step(4) Spaceship.turnLeft() Spaceship.step(3)2、 Spaceship.step() Spaceship.turnLeft() Spaceship.…

学QT的第一天~

#include "mywidget.h" MyWidget::MyWidget(QWidget *parent) : QWidget(parent) { //窗口相关设置// this->resize(427,330); this->setFixedSize(427,330); //设置图标 this->setWindowIcon(QIcon("C:\\Users\\Admin\\Desktop\\pictrue\\dahz.jpg&q…

【面试经典 150 | 分治】建立四叉树

文章目录 写在前面Tag题目来源解题思路方法一&#xff1a;递归 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法&#xff0c;两到三天更新一篇文章&#xff0c;欢迎催更…… 专栏内容以分析题目为主&#xff0c;并附带一些对于本题涉及到的数据结构等内容进行回顾…

C语言写的LLM训练

特斯拉前 AI 总监、OpenAI 创始团队成员 Andrej Karpathy 用 C 代码完成了 GPT-2 大模型训练过程&#xff1a;karpathy/llm.c: LLM training in simple, raw C/CUDA (github.com) 下载源码 git clone --recursive https://github.com/karpathy/llm.c.git下载模型 从HF-Mirro…

JavaScript中的RegExp和Cookie

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;JavaScript 精粹 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 &#x1f506;RegExp &#x1f3b2; 1 什么是正则表达式 &#x1f3b2;2 创建…

组件化开发根组件

目录 一、组件化开发介绍 二、根组件 一、组件化开发介绍 组件化&#xff1a;一个页面可以拆分成一个个组件&#xff0c;每个组件有着自己独立的结构、样式、行为。 好处&#xff1a;便于维护&#xff0c;利于复用&#xff0c;提升开发效率。 二、根组件 组件分类&#xff…

MindSponge分子动力学模拟——安装与使用

技术背景 昇思MindSpore是由华为主导的一个&#xff0c;面向全场景构建最佳昇腾匹配、支持多处理器架构的开放AI框架。MindSpore不仅仅是软件层面的工具&#xff0c;更重要的是可以协同华为自研的昇腾Ascend平台&#xff0c;做到软硬件一体的行业解决方案。基于MindSpore的高通…
最新文章