数据结构复习指导之绪论(算法的概念以及效率的度量)

文章目录

绪论:

2.算法和算法评价

知识总览

2.1算法的基本概念

知识点回顾与重要考点

2.2算法效率的度量

知识总览

1.时间复杂度

2.空间复杂度

知识点回顾与重要考点

归纳总结


绪论:

2.算法和算法评价

知识总览

2.1算法的基本概念

算法( Algorithm)是对特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。此外,一个算法还具有下列五个重要特性:

1)  有穷性。一个算法必须总在执行有穷步之后结束,且每一步都可在有穷时间内完成。

2)确定性。算法中每条指令必须有确切的含义,对于相同的输入只能得出相同的输出。

3)可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。

4)输入一个算法有零个或多个输入,这些输入取自于某个特定的对象的集合。

5)输出一个算法有一个或多个输出,这些输出是与输入有着某种特定关系的量。通常,设计一个“好”的算法应考虑达到以下目标:

        1)   正确性。算法应能够正确地解决求解问题。

        2)可读性。算法应具有良好的可读性,以帮助人们理解。

        3)健壮性。算法能对输入的非法数据做出反应或处理,而不会产生莫名其妙的输出。

        4)高效率与低存储量需求。效率是指算法执行的时间,存储量需求是指算法执行过程中所
        需要的最大存储空间,这两者都与问题的规模有关。

知识点回顾与重要考点

2.2算法效率的度量

知识总览

1.时间复杂度

一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n),它是该算法问题规模n的函数,时间复杂度主要分析T(n)的数量级。

算法中基本运算(最深层循环中的语句)的频度与T(n)同数量级,因此通常将算法中基本运算的执行次数的数量级作为该算法的时间复杂度。于是,算法的时间复杂度记为T(n)=O(f(n))

式中,O的含义是T(n)的数量级,其严格的数学定义是:若T(n)和 fn)是定义在正整数集合上的两个函数,则存在正常数C和n,使得当n≥n时,都满足0≤T(n)≤Cf(n)。

算法的时间复杂度不仅依赖于问题的规模n,也取决于待输入数据的性质(如输入数据元素的初始状态)。例如,在数组A [ 0...n- 1]中,查找给定值k的算法大致如下:

i=n-l;
while (i>=0&&(A[i]!=k))
i--;
return i;

该算法中语句3(基本运算)的频度不仅与问题规模n有关,而且与下列因素有关:

若A中没有与k相等的元素,则语句3的频度f(n)=n。
②若A的最后一个元素等于k,则语句3的频度f(n)是常数0。最坏时间复杂度是指在最坏情况下,算法的时间复杂度。


平均时间复杂度是指所有可能输入实例在等概率出现的情况下,算法的期望运行时间。

最好时间复杂度是指在最好情况下,算法的时间复杂度。

一般总是考虑在最坏情况下的时间复杂度,以保证算法的运行时间不会比它更长。在分析一个程序的时间复杂性时,有以下两条规则:

1)加法规则:T(n)=T(n)+T,(n)=O(f(n))+O(gn))=O(max(f(n), g(n))

2)乘法规则: T(n)=T(n)xT;(n)=O(f(n))×O(g(n))=o(f (n)×g(n))

2.空间复杂度

算法的空间复杂度S(n)定义为该算法所需的存储空间,它是问题规模n的函数,记为

S(n)=O(g(n))

一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身,和算法无关,则只需分析除输入和程序之外的额外空间。例如,若算法中新建了几个与输入数据规模n相同的辅助数组,则空间复杂度为O(n)。

算法原地工作是指算法所需的辅助空间为常量,即O(1)。


知识点回顾与重要考点

归纳总结

本章的重点是分析程序的时间复杂度。一定要掌握分析时间复杂度的方法和步骤,很多读者
在做题时一眼就能看出在厅出的两种形式,供大家参考。人众多资料,总结出了此类题型的两种形式,供大家参考。

1.循环主体中的变量参与循环条件的判断
在用于递推实现的算法中,首先找出基本运算的执行次数x与问题规模n之间的关系式,解得x=f(n),f(n)的最高次幂为k,则算法的时间复杂度为O(n的)。例如,

1.

int i=1;
while(i<=n)
i=i*2;

2.

int y=5;
while((y+1)*(y+1)<n)
y=y+1;


在例1中,设基本运算i=i*2的执行次数为t,则2^{t}\leqslant n,解得t\leqslant \log_{2}n,故 T(n)=O(\log_{2}n)

在例2中,设基本运算y=y+1的执行次数为t,则t=y-5,且(t+5+1)(t+5+1)<n,解得t<√n-6,即 T(n)= O( √n )。

2.循环主体中的变量与循环条件无关
此类题可采用数学归纳法或直接累计循环次数。多层循环时从内到外分析,忽略单步语句、条件判断语句,只关注主体语句的执行次数。

此类问题又可分为递归程序和非递归程序:

·递归程序一般使用公式进行递推。时间复杂度的分析如下:
T(n)=1+T(n-1)=1+1+T(n-2)=…=n-1+ T(1)
即T(n)=O(n)

·非递归程序的分析比较简单,可以直接累计次数。
 

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

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

相关文章

一辆汽车的节拍时间是怎样的?

节拍时间&#xff0c;又称 takt time&#xff0c;是德语中“节奏”的意思。在汽车制造业中&#xff0c;它指的是按照客户需求和生产计划&#xff0c;生产一辆汽车所需的时间。这个时间是固定的&#xff0c;它决定了生产线上每个工序的操作速度和节奏&#xff0c;是生产线上所有…

一题多解之数塔问题

递归实现:记忆化深度遍历 #include <iostream> #include <algorithm> #include <string> using namespace std; int num[1000][1000],n;//递归实现:记忆化深度遍历 int dfs(int x,int y){int sum0;//记录最大情况if(x>n||y>x) return sum;//实现每次都…

功能测试_验证标题长度合法性_边界值法

验证标题长度合法性&#xff08;标题长度大于0&#xff0c;小于等于30个字符&#xff09; 开内闭外&#xff0c;保留1和31

水电智能远程抄表系统

水电智能远程抄表系统是一种应用先进技术实现水电抄表的智能化管理系统&#xff0c;通过远程抄表、数据传输和智能分析&#xff0c;实现了对水电使用情况的实时监测和管理。本文将从系统特点、构成以及带来的效益三个方面展开介绍。 系统特点 1.远程抄表&#xff1a;系统能够…

cas学习4:自定义登出页面

接上一章学习 cas学习3&#xff1a;自定义登录页面_cas 个性化页面-CSDN博客 后我们要自定义登出页面&#xff0c;因为在配置完cas后各个子系统退出后的都是cas登出页面。不符合实际需要&#xff0c;所以我们要配置自己的登出页面 1.修改application.properties 增加&#…

有效确认手机号机主姓名,避免信息错误

在如今信息爆炸的时代&#xff0c;手机已经成为我们生活中必不可少的一部分。手机号码的重要性已经不仅仅是联系工具&#xff0c;更是诸多场景下的实名认证必备条件&#xff0c;如电商、游戏、直播、金融等。为了保证用户信息的准确性和安全性&#xff0c;挖数据平台上的手机号…

软件测试学习之MySQL学习笔记(完结)

目录 1. 数据库**** 1.1. 概念**** 1.2. 分类**** 1.2.1. 关系型数据库**** 1.2.1.1. SQL**** 1.2.2. 安装**** 1.2.2.1. Navicat**** 2. SQL语句**** 2.1. 常用数据类型**** 2.2. 数据库**** 2.3. 表**** 2.3.1. 字段约束**** 2.4. 数据**** 2.4.1. 增 insert**…

AI革新病历系统-能“读懂”病历,或将能“思考”

Artificial Intelligence&#xff08;人工智能&#xff09;&#xff0c;简称AI。它其实是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。 电子病历系统拖慢了医疗工作流程&#xff0c;人工智能或许能改善这一困境。 一位名叫罗杰的…

典型神经网络模型—自编码器

文章目录 编码器的介绍基本原理编码器的分类 应用案例网络构建训练步骤&#xff1a;调优&#xff1a; 编码器的介绍 基本原理 在神经网络中&#xff0c;编码器&#xff08;Encoder&#xff09;是一种用于将输入数据转换为另一种形式的网络组件或模型部分。编码器的核心任务是…

Teachable Machine模型之TensorFlow使用篇

前言: 使用在teachable machine训练的h5格式模型 tensorflow使用篇 1. 使用teachable machine训练模型 地址: 传送门, 需要梯子翻一下 训练后, 导出的时候可以选择三种类型 导出模型文件 converted_keras.zip (py版) 解压后得到 2. py项目中使用模型 根据你当时使用tea…

FFmpeg: 简易ijkplayer播放器实现--06封装打开和关闭stream

文章目录 流程图stream openstream close 流程图 stream open 初始化SDL以允许⾳频输出&#xff1b;初始化帧Frame队列初始化包Packet队列初始化时钟Clock初始化音量创建解复用读取线程read_thread创建视频刷新线程video_refresh_thread int FFPlayer::stream_open(const cha…

Nginx转发请求错误

说明&#xff1a;记录一次使用Nginx转发请求的错误&#xff1b; 场景 公司内部有两台服务器都跑了后端项目&#xff0c;在使用Nginx做请求分发时&#xff0c;我发现其中有台服务器一直没有处理请求&#xff08;没打印相关的日志信息&#xff09;&#xff0c;于是我修改了下Ng…

企业如何使用SNP Glue将SAP与Snowflake集成?

SNP Glue是SNP的集成技术&#xff0c;适用于任何云平台。它最初是围绕SAP和Hadoop构建的&#xff0c;现在已经发展为一个集成平台&#xff0c;虽然它仍然非常专注SAP&#xff0c;但可以将几乎任何数据源与任何数据目标集成。 我们客户非常感兴趣的数据目标之一是Snowflake。Sno…

SpringBoot集成Skywalking链路追踪

安装skywaling 参考&#xff1a;Centos7搭建 SkyWalking 单机版-CSDN博客 下载Agents https://archive.apache.org/dist/skywalking/java-agent/9.0.0/apache-skywalking-java-agent-9.0.0.tgz 1. 在IDEA中使用skywalking agent 在VM options中填入如下信息 -javaagent后是…

LeetCode-2529题:正整数和负整数的最大计数(原创)

【题目描述】 给你一个按 非递减顺序 排列的数组 nums &#xff0c;返回正整数数目和负整数数目中的最大值。换句话讲&#xff0c;如果 nums 中正整数的数目是 pos &#xff0c;而负整数的数目是 neg &#xff0c;返回 pos 和 neg二者中的最大值。注意&#xff1a;0 既不是正整…

windows ffmpeg7 通过rtsp拉取h265裸流

点击下边那个链接会转到github 下载完成后&#xff0c;添加include、lib到工程。 添加头文件&#xff1a; extern "C" { #include "libavcodec/avcodec.h" #include "libavformat/avformat.h" #include "libavformat/avio.h" #inclu…

【实战JVM】打破双亲委派机制之自定义类加载器

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大三在校生&#xff0c;喜欢AI编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;落798. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc;️…

JVS智能BI:嵌套数据集在多层次数据关联中的实战应用

在数据分析平台中&#xff0c;数据集的嵌套调用主要用于处理复杂数据结构或多层次数据关联&#xff0c;或者有多场景使用的重复使用中间数据&#xff0c;那么就需要把某些数据生成中间结果的数据集合。 例如&#xff1a;用户的分类需要根据用户的各方面的数据特征进行分类打标…

算法设计与分析实验报告c++实现(矩阵链相乘问题、投资问题、背包问题、TSP问题、数字三角形)

一、实验目的 1&#xff0e;加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握&#xff1b; 2&#xff0e;提高学生利用课堂所学知识解决实际问题的能力&#xff1b; 3&#xff0e;提高学生综合应用所学知识解决实际问题的能力。 二、实验任务 1、…

自动化测试提速必备 - 并发编程

在自动化测试领域&#xff0c;多线程和多进程技术被广泛应用于提高测试的执行效率和性能。通过并发运行测试用例&#xff0c;可以显著缩短测试周期&#xff0c;特别是在面对大量测试用例或者需要在多个环境中进行测试时尤为重要。 在实际的自动化测试中&#xff0c;我们经常碰…