算法的基础知识

算法的定义

算法是为了解决某类问题而规定的一个有限长的操作序列

算法的特性

1. 有穷性(Finiteness)
  • 含义:一个算法必须总是在执行有穷步后结束,且每一步都必须在有穷时间内完成。
  • 重要性:确保算法能够在合理的时间内完成,不会陷入无限循环。
2. 确定性(Definiteness)
  • 含义:对于每种情况下所应执行的操作,在算法中都有确切的规定,不会产生二义性,算法的执行者或阅读者都能明确其含义及如何执行。
  • 重要性:确保算法的每一步都可以被精确执行,不同的人执行同一算法会得到相同的结果。
3. 可行性(Effectiveness)
  • 含义:算法中的所有操作都可以通过将已经实现的基本操作运算执行有限次来实现。
  • 重要性:确保算法不仅是理论上的,而且是实际可执行的,可以通过现有的技术手段实现。
4. 输入(Input)
  • 含义:一个算法有0个或多个输入。当用函数描述算法时,输入往往是通过形参表示的,在它们被调用时,从主调函数获得输入值。
  • 重要性:输入是算法处理的基础,没有输入,算法无法开始执行。在函数形式中,输入通常通过参数传递。
5. 输出(Output)
  • 含义:一个算法有一个或多个输出,它们是算法进行信息加工后得到的结果,无输出的算法没有任何意义。当用函数描述算法时,输出多用返回值或引用类型的形参表示。
  • 重要性:输出是算法执行的目的。

评价算法优劣的基本标准

应该从以下几方面来评价

1.正确性:

在合理的数据输入下,好的算法能够在有限的运行时间内得到正确的结果

2.可读性:

一个好的算法,首先应便于人们理解和相互交流,其次才是机器可执行性。可读性强的算法有助于人们对算法的理解,而难懂的算法容易隐藏错误,且难于调试和修改。

3.健壮性:

当输入的数据非法时,好的法能适当地做出正确反应或进行相应处理,而不会产生一些莫名其妙的输出结果。

4.高效性:

高效性包括时间和空间两个方面。时间高效是指算法设计合理,执行效率高,可以用时间复杂度来度量;空间高效是指算法占用存储容量合理,可以用空间复杂度来度量。时间复杂度和空间复杂度是衡量算法的两个主要指标。

算法时间复杂度

1. 时间复杂度的重要性

算法的时间复杂度是衡量算法执行时间随输入规模增长的变化趋势。它帮助我们评估算法的效率,并在多个算法中选择最优解。

2. 时间复杂度的基本概念
  • 问题规模:用整数n表示,不同问题中n的含义不同。
  • 语句频度:一条语句的重复执行次数,直接影响算法的执行时间。

设每条语句执行一次所需的时间均是单位时间,则一个算法的执行时间可用该算法中所有语句频度之和来度量。

3. 时间复杂度的定义
  • 基本语句:算法中重复执行次数和算法的执行时间成正比的语句,它对算法运行时间的贡献最大。
  • 渐近时间复杂度:一般情况下,算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作: T(n) = O(f(n))
    它表示随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度(Time Complexity)。
4. 时间复杂度的数学定义
  • O符号:表示数量级:
    在这里插入图片描述
5. 时间复杂度的分析方法
  • 找出基本语句:确定算法中执行次数最多的语句。
  • 计算频度:计算基本语句的频度,得到问题规模n的函数f(n)。
  • 确定数量级:用O符号表示f(n)的数量级。
6. 时间复杂度的常见类型
  • 常量阶:O(1)
  • 对数阶:O(log n)
  • 线性阶:O(n)
  • 平方阶:O(n^2)
  • 立方阶:O(n^3)
  • k次方阶:O(n^k)
  • 指数阶:O(2^n)
常量阶示例
{x++; s=0;}
  • 频度:两条语句的频度都是1。
  • 时间复杂度:T(n) = O(1),与输入规模n无关。
线性阶示例
for(i=0; i<n; i++) { x++; s=0; }
  • 频度:循环执行n次。
  • 时间复杂度:T(n) = O(n),与输入规模n线性相关。
立方阶示例
for(k=1; k<=n; k++)for(i=1; i<=n; i++)for(j=1; j<=n; j++)y++;
  • 频度:最内层循环的频度为n^3。
  • 时间复杂度:T(n) = O(n^3),与输入规模n的立方相关。
for(i=1; i<=n; i++)for(j=1; j<=i; j++)for(k=1; k<=j; k++)x++;
  • 频度:总频度大约为n^3/6。
  • 时间复杂度:T(n) = O(n^3),与输入规模n的立方相关。
对数阶示例
for(i=1; i<=n; i=i*2)x++;
  • 频度:需要log2(n)次循环。
  • 时间复杂度:T(n) = O(log2n),与输入规模n的对数相关。
7. 最好、最坏和平均时间复杂度
  • 最好时间复杂度:算法在最好情况下的时间复杂度,是指算法计算量可能达到的最小值;
  • 最坏时间复杂度:算法在最坏情况下的时间复杂度,是指算法计算量可能达到的最大值;
  • 平均时间复杂度:算法在所有可能情况下,按照输入实例以等概率出现时,算法计算量的加权平均值。
  • 通常只讨论算法在最坏情况下的时间复杂度,即分析在最坏情况下,算法执行时间的上界。
最好、最坏和平均时间复杂度示例
for(i=0; i<n; i++)if(a[i] == e) return i+1;
return 0;
  • 最好情况:如果e是第一个元素,频度为1。
    • 最好时间复杂度:T(n) = O(1)
  • 最坏情况:如果e是最后一个元素或不存在,频度为n。
    • 最坏时间复杂度:T(n) = O(n)
  • 平均情况:假设e在数组中任意位置出现的概率相等,平均频度为n/2。
    • 平均时间复杂度:T(n) = O(n)

算法空间复杂度

算法的空间复杂度是衡量算法在执行过程中所需的存储空间的量度,类似于时间复杂度,它也是问题规模n的函数,记作S(n) = O(f(n))。

1. 空间复杂度的定义
  • 渐近空间复杂度:算法所需存储空间的量度,是问题规模n的函数。
  • 辅助空间:除了输入数据本身,算法执行时还需要一些对数据进行操作的辅助存储空间。
2. 空间复杂度的分类
  • 原地工作:如果算法执行时所需要的辅助空间相对于输入数据量而言是个常数,则称这个算法在原地工作,辅助空间为O(1)。
  • 非原地工作:如果算法需要占用的临时工作单元数与问题规模n有关,则空间复杂度为O(n)或其他。
例:数组逆序
  • 算法1

    for(i=0; i<n/2; i++) {t = a[i];a[i] = a[n-i-1];a[n-i-1] = t;
    }
    
    • 分析:算法1仅需要一个额外的变量t来交换元素,与问题规模n大小无关。
    • 空间复杂度:S(n) = O(1)。
  • 算法2

    for(i=0; i<n; i++)b[i] = a[n-i-1];
    for(i=0; i<n; i++)a[i] = b[i];
    
    • 分析:算法2需要一个大小为n的辅助数组b来存储逆序后的元素。
    • 空间复杂度:S(n) = O(n)。

时间复杂度与空间复杂度的关系

  • 相互影响:追求较好的时间复杂度可能会导致占用较多的存储空间,反之亦然。
  • 权衡:在实际应用中,通常更关注算法的时间复杂度,因为运算空间相对充足。

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

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

相关文章

城镇保障性住房管理:SpringBoot技术应用

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常…

【ComfyUI】flux人像摄影风格迁移的最优解?这个效果应该暂时无敌了吧?效果不好你打我!

大家好&#xff0c;这期我们主要讨论如何使用stable diffusion comfyUI 制作基于flux的人像摄影&#xff0c;主要实现风格迁移的功能。 我们都知道flux的生态目前不太完善&#xff0c;flux的controlnet和flux ipadapter虽然有&#xff0c;但效果不太好&#xff0c;可控性不强。…

基于微信的追星小程序+ssm(lw+演示+源码+运行)

摘 要 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;追星小程序被用户普遍使用&#xff0c;为方便用户能够可以…

esp32cam+Arduino IDE在编译时提示找不到 esp_camera.h 的解决办法

多半是因为你的ESP32库升级了&#xff0c;不再是 1.02版本&#xff0c;或者根本就没有 ESp32 库。如果被升级了&#xff0c;还原为1.02版本就可以了。如果没有&#xff0c;按照下述方法添加&#xff1a; 首先&#xff0c;在"文件"->"首选项"->"…

基于物联网设计的地下煤矿安全监测与预警

文章目录 一、前言1.1 项目介绍【1】项目开发背景【2】设计实现的功能【3】项目硬件模块组成 1.2 设计思路1.3 系统功能总结1.4 开发工具的选择【1】设备端开发【2】上位机开发 1.5 模块的技术详情介绍【1】NBIOT-BC26模块【2】MQ5传感器【4】DHT11传感器【5】红外热释电人体检…

第8章 利用CSS制作导航菜单作业

1.利用CSS技术&#xff0c;结合链接和列表&#xff0c;设计并实现“山水之间”页面。 浏览效果如下&#xff1a; HTML代码如下&#xff1a; <!DOCTYPE html> <html><head><meta charset"utf-8" /><title>山水之间</title><…

32单片机HAL库的引脚初始化

在使用HAL库时&#xff0c;GPIO初始化函数定义在stm32f4xx_hal_gpio.c文件中&#xff0c;如下&#xff1a; void HAL_GPIO_Init(GPIO_TypeDef *GPIOx, GPIO_InitTypeDef *GPIO_Init); 由这个函数可以看出&#xff0c;在初始化GPIO时&#xff0c;需要向函数传入2个结构体&…

Django安装

在终端创建django项目 1.查看自己的python版本 输入对应自己本机python的版本&#xff0c;列如我的是3.11.8 先再全局安装django依赖包 2.在控制窗口输入安装命令&#xff1a; pip3.11 install django 看到Successflully 说明我们就安装成功了 python的Scripts文件用于存…

网络层5——IPV6

目录 一、IPv6 vs IPv4 1、对IPv6主要变化 2、IPv4 vs IPv6 二、IPv6基本首部 1、版本——4位 2、通信量类——8位 3、流标号——20位 4、有效载荷长度——16位 5、下一个首部——8位 6、跳数限制——8位 7、源 、 目的地址——128位 8、扩展首部 三、IPv6地址 1…

怎么样鉴定疾病相关稀有细胞群?二值化精细模型标签,这个刚发的顶刊单细胞算法值得一学!

生信碱移 HiDDEN&#xff1a;抽丝剥茧 在具有病例和对照单细胞RNA测序研究中&#xff0c;样本级标签通常被直接赋予单个细胞&#xff0c;假设所有病例细胞都受影响。这种传统方法在受影响细胞比例较小或扰动强度较弱时&#xff0c;难以有效识别关键细胞及其标记基因&#xff…

三周精通FastAPI:33 在编辑器中调试

官方文档&#xff1a;https://fastapi.tiangolo.com/zh/tutorial/debugging/ 调试 你可以在编辑器中连接调试器&#xff0c;例如使用 Visual Studio Code 或 PyCharm。 调用 uvicorn 在你的 FastAPI 应用中直接导入 uvicorn 并运行&#xff1a; import uvicorn from fast…

Spring Boot关闭时,如何确保内存里面的mq消息被消费完?

1.背景 之前写一篇文章Spring Boot集成disruptor快速入门demo&#xff0c;有网友留言如下图&#xff1a; 针对网友的留言&#xff0c;那么我们如何解决这个问题呢 Spring-Boot应用停机时&#xff0c;如何保证其内存消息都处理完成&#xff1f; 2.解决方法 方法其实挺简单的&…

vue3+vite搭建脚手架项目使用eletron打包成桌面应用+可以热更新

当前Node版本&#xff1a;18.12.0&#xff0c;npm版本&#xff1a;8.19.2 1.搭建脚手架项目 搭建Vue3ViteTs脚手架-CSDN博客 可删掉index.html文件的title标签 2.配置package.json {"name": "my-vite-project","private": true,"versi…

【Golang】validator库的使用

package mainimport ("fmt""github.com/go-playground/validator" )// MyStruct .. validate:"is-awesome"是一个结构体标签&#xff0c;它告诉验证器使用名为is-awesome的验证规则来验证String字段。 type MyStruct struct {String string vali…

Linux(CentOS)安装 MySQL

CentOS版本&#xff1a;CentOS 7 MySQL版本&#xff1a;MySQL Community Server 8.4.3 LTS 1、下载 MySQL 打开MySQL官网&#xff1a;https://www.mysql.com/ 直接下载网址&#xff1a;https://dev.mysql.com/downloads/mysql/ 其他版本 2、上传 MySQL 文件到 CentOS 使用F…

Pytorch实现transformer语言模型

转载自&#xff1a;| 03_language_model/02_Transformer语言模型.ipynb | 从头训练Transformer语言模型 |Open In Colab | Transformer语言模型 本节训练一个 sequence-to-sequence 模型&#xff0c;使用pytorch的 nn.Transformer <https://pytorch.org/docs/master/nn.ht…

<Project-20 YT-DLP> 给视频网站下载工具 yt-dlp/yt-dlp 加个页面 python web

介绍 yt-dlp Github 项目&#xff1a;https://github.com/yt-dlp/yt-dlp A feature-rich command-line audio/video downloader 一个功能丰富的视频与音频命令行下载器 原因与功能 之前我用的 cobalt 因为它不再提供Client Web功能&#xff0c;只能去它的官网使用。 翻 redd…

Sqli-Labs

目录 解题思路 题目设计原理 总结 解题思路 什么&#xff1f;sqli-labs&#xff1f;让我看看。还真是。想起了当初刚学被支配的恐惧。 悄咪咪点开第一关看看能不能秒了。测试闭合老样子&#xff0c;单引号闭合&#xff0c;双引号等都成功。这里 and 11 和 # 都不能通过检测&…

【基于Zynq FPGA对雷龙SD NAND的测试】

一、SD NAND 特征 1.1 SD 卡简介 雷龙的 SD NAND 有很多型号&#xff0c;在测试中使用的是 CSNP4GCR01-AMW 与 CSNP32GCR01-AOW。芯片是基于 NAND FLASH 和 SD 控制器实现的 SD 卡。具有强大的坏块管理和纠错功能&#xff0c;并且在意外掉电的情况下同样能保证数据的安全。 …

【NOIP提高组】引水入城

【NOIP提高组】引水入城 &#x1f490;The Begin&#x1f490;点点关注&#xff0c;收藏不迷路&#x1f490; 在一个遥远的国度&#xff0c;一侧是风景秀美的湖泊&#xff0c;另一侧则是漫无边际的沙漠。该国的行政 区划十分特殊&#xff0c;刚好构成一个N行M列的矩形&#xff…