【数据结构】算法的时间复杂度与空间复杂度

计算机考研408-数据结构笔记本之——第一章 绪论

1.2 算法和算法评价

1.2.2 算法效率的度量

算法效率的度量是通过时间复杂度和空间复杂度来描述的。

1.时间复杂度

时间复杂度T(n)是事前预估算法时间开销T(n)问题规模 n 的关系(T 表示 “time”),通常将算法中基本运算的执行次数的数量级作为该算法的时间复杂度,记为:T(n) = O(f(n)) 

2.计算时间复杂度

以【算法表白——爱你n遍】举例。

算法1中,语句频度: ① ——1次 ② ——3001次 ③④ ——3000次 ⑤ ——1次 (注:一个语句的频度是指该语句在算法中被重复执行的次数),易得:问题规模 n = 3000,时间开销T(n) = 1 + 3001 + 3000 + 1 = 3n + 3

这样就简单计算出了算法1的T(n).

当遇到复杂的算法时,这样的粗暴计算难免会很麻烦,是否可以忽略表达式某些部分?

答:可以。如同上面提到的,只考虑阶数,用大O记法 O(f(n)) 来表示T(n) ,下图是一个简单的演示:

简单总结就是,只取最高阶项,并视最高阶项系数为1.  并遵循下列两个规则:

那么,如何知道哪一项是算式中的最高阶呢?请记住下表(可以用求极限的方法来判断,平常使用记住即可):(口诀:从小到大,常对幂指阶

但是,如果有好几千行代码,难道依然要像算法1一样一行一行看,计算每一行的语句频度么?

答:当然不。只需考虑最深层循环的循环次数与 n 的关系即可。

如下图:

结论1:顺序执行的代码只会影响常数项,可以忽略

结论2:只需挑循环中的一个 基本操作分析它的执行次数与 n 的关系即可

结论3:如果有多层嵌套循环,只需关注最深层循环循环了几次

一眼不能看出最深层循环频度时,可像下图一样,设置一个x求时间复杂度

当时间复杂度如算法4一样受概率或其他因数影响大小时,我们将最坏情况时间复杂度视为该算法时间复杂度。

补充:三种时间复杂度

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

眼在手外-机器人坐标系与相机坐标系标定方法

1 眼在手外坐标系概述 实现机械臂和相机的手眼标定,就是要通过双目相机坐标系、机械臂坐标系和机械臂 末端执行器三者的坐标系转换,求出手眼转换矩阵。设双目相机坐标系为 Oc,标定板坐标 系为 Ow,末端执行器坐标系为 Oe&#xff0…

【C++】二维数组定义方式

二维数组有四种定义方式 1、数据类型 数组名[行数 ][ 列数 ]; 2、数据类型 数组名[ 行数 ][ 列数 ]{{数据1,数据2},{数据3,数据4 }}; 3、数据类型 数组名[ 行数 ][ 列数 ]{数据1,数据2,数据3&#xff…

Java | Leetcode Java题解之第321题拼接最大数

题目&#xff1a; 题解&#xff1a; class Solution {public int[] maxNumber(int[] nums1, int[] nums2, int k) {int m nums1.length, n nums2.length;int[] maxSubsequence new int[k];int start Math.max(0, k - n), end Math.min(k, m);for (int i start; i < e…

04 表的操作

目录 创建查看修改删除 1. 创建 语法&#xff1a; CREATE TABLE table_name ( field1 datatype, field2 datatype, field3 datatype ) character set 字符集 collate 校验规则 engine 存储殷勤; 说明&#xff1a; field&#xff0c;表示列名 datatype&#xff0c;表示列的类型…

C++ 继承 派生类的拷贝构造

继承 派生类的拷贝构造构造顺序拷贝构造 引例1: 当子类,不自实现拷贝构造时,默认调用父类的拷贝构造引例2: 子类自实现拷贝构造,不做特殊处理时,只会调用父类的构造器.引例3: 显示的调用父类的拷贝构造器。案例: 内嵌函数的拷贝构造 引例1 :当内嵌子对象,子类不自实现拷贝构造时…

【java】单行注释(//)与多选注释(/* */)

文章目录 单行注释多行注释注意事项 在Java中&#xff0c;注释是用来给代码添加说明的&#xff0c;它不会被编译器执行。Java提供了两种主要的注释方式&#xff1a;单行注释和多行注释&#xff08;有时也称为块注释或块级注释&#xff09;。 单行注释 单行注释以两个正斜杠&…

数模评价决策类—熵权法

目录 文章目录 前言 一、熵权法是什么&#xff1f; 二、基本步骤 计算样本权重及熵权 总结 前言 前面我们学习了层次分析法和Topsis法&#xff0c;这两个方法都是偏主观的方法&#xff0c;这篇我们将运用较为客观的方法——熵权法&#xff0c;做出决策 一、熵权法是什么…

JavaWeb-HTML

一、HTML&CSS&JavaSript的作用: 1.HTML主要用于网页为主体结构的搭建&#xff1b; 2.CSS主要用于页面元素的美化 3.JavaScript主要用于页面元素的动态处理; 二、HTML HTML是Hyper Text Markup Language的缩写。意思是超文本标记语言。它的作用是搭建网页结构&…

2024死磕小红书,一定能赚到钱!

​2024死磕小红书&#xff0c;一定能赚到钱&#xff01;在文末领取小红书运营完全指南电子书 从2023年起&#xff0c;小红书这股热乎劲儿就像开了挂&#xff0c;突然间就成了人人想蹭的“显学”。大伙儿都想趁着平台红利期&#xff0c;分一杯羹。说来惭愧&#xff0c;我从2020年…

牛顿插值法代替泰勒公式

引入 例题 近似函数&#xff1a; 通过这个近似函数可以看出&#xff0c;若要证的函数超过二阶可导&#xff0c;那么就不适合用牛顿插值法代替泰勒公式 因为&#xff0c;后面的操作非常复杂&#xff0c;不划算了… 总结 我们可以通过牛顿插值法生成一个逼近曲线的直线&#xf…

使用Python库开发Markdown编辑器并将内容导出为图片

简介 在本文中&#xff0c;我们将探索如何使用Python的wxPython库开发一个Markdown编辑器应用程序。这个应用程序不仅能浏览和编辑Markdown文件&#xff0c;还可以将编辑的内容导出为PNG图片。 C:\pythoncode\new\markdowneditor.py 完整代码 import wx import markdown2 im…

【传知代码】实体关系抽取(论文复现)

当谈论信息提取领域的最前沿时&#xff0c;实体关系抽取无疑是其中一颗耀眼的明星。从大数据时代的信息海洋中提炼出有意义的关系&#xff0c;不仅是科技进步的体现&#xff0c;更是人类对知识管理和智能决策迫切需求的响应。本文将探索实体关系抽取的核心技术、应用场景及其在…

太阳光模拟器在光纤中的应用

概述 太阳光模拟器是一种重要的实验室设备&#xff0c;它能模拟太阳光的光谱、强度和角度分布&#xff0c;广泛应用于光纤通信、光电器件测试、太阳能研究等多个领域。通过模拟太阳光的光照条件&#xff0c;研究人员可以在实验室环境中对光电材料和器件进行性能测试和研究。 太…

二维码生成原理及解码原理

☝☝☝二维码配图 二维码 二维码&#xff08;Quick Response Code&#xff0c;简称QR码&#xff09;是一种广泛使用的二维条形码技术&#xff0c;由日本公司Denso Wave在1994年开发。二维码能有效地存储和传递信息&#xff0c;广泛应用于商品追溯、支付、广告等多个领域。二维…

c++入门基础(下篇)————引用、inline、nullptr

引用 引用的概念和定义 引⽤不是新定义⼀个变量&#xff0c;⽽是给已存在变量取了⼀个别名&#xff0c;编译器不会为引⽤变量开辟内存空间&#xff0c; 它和它引⽤的变量共⽤同⼀块内存空间。 类型& 引用别名 引用对象; 就像孙悟空也叫齐天大圣 猪八戒也叫天蓬元帅。…

Meinberg Lantime服务器监控指标解读

监控易是一款功能强大的IT基础设施监控软件&#xff0c;它能够实时监控各种IT设备的状态&#xff0c;提供全面的性能分析和告警通知服务。对于Meinberg Lantime服务器&#xff0c;监控易通过一系列监控指标&#xff0c;确保服务器的稳定运行和服务的可用性。 一、监控对象概述…

策略模式的一次应用

项目的需求是将一组图像按照相似度分类。 采用了模板匹配计算相似度的实现方式。 #include <opencv2/core.hpp> #include <openev2/core/utility.hpp> #include <opencv2/highqui.hpp> #include <openav2/imgproc.hpp> cv::Mat image matched; double …

Linux系统编程 --- 动静态库

一、回顾&#xff0c;制作一个库 libXXX.a --- 静态链接 libYYY.so --- 动态链接 设计一个库&#xff1a; 把我们提供的方法&#xff0c;给别人用&#xff1a; 1、把源文件直接给他 2、把我们的源代码打包成库 库 头文件。 原理&#xff1a;把所有的.o文件打包成.a文件也…

llama神经网络的结构,llama-3-8b.layers=32 llama-3-70b.layers=80; 2000汉字举例说明

目录 llama-3-8b.layers=32 llama-3-70b.layers=80 llama神经网络的结构 Llama神经网络结构示例 示例中的输入输出大小 实际举例说明2000个汉字文本数据集 初始化词嵌入矩阵 1. 输入层 2. 嵌入层 3. 卷积层 4. 全连接层 llama-3-8b.layers=32 llama-3-70b.laye…

如何快速看完一个网页上的视频

如何快速看完一个视频 懂的都懂。 Edge浏览器 添加下面两个书签&#xff1a; javascript:document.querySelector("video").dispatchEvent(new Event("ended"))javascript:var vdocument.querySelector("video");if(v){v.mutedtrue;v.playba…