国家高新技术企业有哪些/seo怎么刷排名
今天对算法产生了兴趣,开始学习基础算法,比如排序,模拟,贪心,递推等内容,算法是很重要的,它是解决某个问题的特定方法,程序=数据结构+算法,所以对算法的学习是至关重要的,它可以提高程序效率,不同的算法也是有优劣的,如何进行评价,这也是我们需要知道的,我会在学习中穿插这种评价方法,下面让我们看看第一个基础算法排序中的选择排序。
1.选择排序的实现
选择排序(SelectionSort)算法的工作原理是每一次遍历从待排序的元素中选出最小(或最大)的一个元素,将其放在已经排好序的数列之后,直到全部排好序为止。
其核心就是选择和交换,流程如下:
假如给定初始数据 8 4 2 7 3(红色为每次遍历交换的数据)
第一次排序 2 4 8 7 3
第二次排序 2 3 8 7 4
第三次排序 2 3 4 7 8
首先在未排序序列中找到最小(或最大)元素,放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小(或最大)元素,然后放到已排序序列的末尾,直到所有元素全部排好序。
逻辑是这样:
(1)第一轮从下标为 1 到下标为 n-1 的元素中选取最小值,若小于第一个数,则交换
(2)第二轮从下标为 2 到下标为 n-1 的元素中选取最小值,若小于第二个数,则交换
依次类推下去……
我们可以再看一个动画演示加深对过程的理解,本图非本人所作,借鉴别人的。
下面是代码实现:
void selectionSort(int arr[],int len)
{int i,j,min,temp;for(i=0;i<len-1;i++){min=i;//先定义一个最小值对应的下标for(j=i+1;j<len;j++){if(arr[min]>arr[j])//如果大于就更新最小值对应的下标{min=j;}}temp=arr[min];//循环结束,找到本次待排序序列的最小值,和序列首元素进行交换,之后进入下一次循环arr[min]=arr[i];arr[i]=temp;}
}
或者下面这个版本
void selectSort(int arr[], int n) {if(n==0||n==1)return;int i, j, minIndex;for (int i = 0; i < n - 1; i++) {minIndex = i;//先定义最小值对应的下标for (int j = i + 1; j < n-1; j++){minIndex = arr[j] < arr[minIndex] ? j : minIndex;//如果小于就更新最小值下标}int temp=arr[min];//循环结束,找到本次待排序序列的最小值,和序列首元素进行交换,之后进入下一次循环arr[min]=arr[i];arr[i]=temp;}
}
2.选择排序的时间复杂度
时间复杂度?这是什么玩意?别搞我啊?可能大家在看到这个词的心理状态是这样的,但你先别急。
2.1 时间复杂度
时间复杂度是用来评价算法性能的,它是用来方便开发者估算程序的运行时间,我们如何估计程序运行时间呢?我们通常会估计算法的操作单元数量,来代表程序消耗的时间
假设算法道德问题规模为n,那么操作单元数量就用函数f(n)来表示,随着n的增大,算法执行时间的增长率和f(n)的增长率相同,这就称作算法的时间复杂度,记为O(f(n))。
大O用来表示上界的,当用它作为算法的最坏情况运行时间的上界,就是对任意数据输入的运行时间的上界。
2.2 如何描述时间复杂度
决定使用哪个算法不仅仅要考虑时间复杂度,不是时间复杂越低的越好,要考虑数据规模,如果数据规模很小,甚至可以用O(n^2)的算法比 O(n)的更合适,就像上图中图中 O(5n^2) 和O(100n) 在n小于2的时候 O(5n^2)是更优的,所花费的时间也是最少的。
那我们为什么在计算时间复杂度的时候要忽略常数项系数呢,也就说O(100n) 就是O(n)的时间复杂度,并且要默认O(n) 优于O(n^2) 呢 ?
因为大O其实就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度,也就是刚才说的上界,在这个时候,常数项系数已经不起决定性作用了,所以可以省略。
例如上图中 20 就是那个点 ,n只要大于20 常数项系数已经不起决定性作用了,其实也包括除最高次数项的其他项。
所以我们说的时间复杂度都是省略常数项系数的,是因为一般情况下我们都是默认数据规模足够的大,基于这样的事实 我们给出的算法时间复杂的的一个排行如下所示:
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
这里只是大概列出概念,后面会专门写一篇来讲这方面的问题。
2.3 选择排序的时间复杂度
从上面的代码我们可以知道选择排序套用了两个循环:
for(i=0;i<n-1;i++)
{for(j=i+1;j<n;j++){}}
很显然问题规模是n,问题规模就是需要解决问题处理数据量的大小,显然是处理n个元素的排序问题,规模为n。
当i=0时,下面内循环比较n-1次,每次i+1下面内循环比较n-i次,因此总共循环次数(操作单元数量)为(n-1)+(n-2)+......+2+1=n^2/2,舍去最高项系数,时间复杂度为O(n^2)。
3.leetcode题目
3.1 颜色分类
void sortColors(int* nums, int numsSize) {int i,j,min,temp;for(i=0;i<numsSize-1;i++){min=i;for(j=i+1;j<numsSize;j++){if(nums[min]>nums[j]){min=j;}}temp=nums[min];nums[min]=nums[i];nums[i]=temp;}
}
这个没什么好说的,就是排序,太水了,模板题。
3.2 至少是其他数字两倍的最大数
int dominantIndex(int* nums, int numsSize) {if(numsSize==1)return 0;int max=0;for(int i=0;i<numsSize;i++){if(nums[max]<nums[i])max=i;}int minindex=0;for(int i=0;i<numsSize-1;i++){minindex=i;for(int j=i+1;j<numsSize;j++){minindex=nums[j]<nums[minindex]?j:minindex;}if(i!=minindex){int temp=nums[i];nums[i]=nums[minindex];nums[minindex]=temp;}}if(nums[numsSize-1]>=2*nums[numsSize-2])return max;else return -1;
}
这个题也不难,关键在于我们要先记录最大数对应的下标,因为我们排序后会破坏原来的顺序,再就是我们只需要判断排序后最后一个数是不是至少是前一个数的两倍,如果这个满足,那这个最大数也必然是其他是的至少两倍。
3.3 判断能否形成等差数列
bool canMakeArithmeticProgression(int* arr, int arrSize) {for(int i=0;i<n;i++){int minindex=i;for(int j=i+1;j<n;j++){minindex=nums[j]<nums[minindex]?j:minindex;}int temp=nums[i];nums[i]=nums[minindex];nums[minindex]=temp;}int d=arr[1]-arr[0];for(int i=2;i<arrSize;i++){if((arr[i]-arr[i-1])!=d)return false;}return true;
}
这个题就是先排序,这样我们就可以很容易的判断,先假定公差为前两个数之差,如果遍历后面相邻两个数之差等于该公差,那说明是等差数列,否则不是。
相关文章:

基础算法(1):排序(1):选择排序
今天对算法产生了兴趣,开始学习基础算法,比如排序,模拟,贪心,递推等内容,算法是很重要的,它是解决某个问题的特定方法,程序数据结构算法,所以对算法的学习是至关重要的&a…...

GeoTrust OV证书
当谈到网站安全性和可信度时,GeoTrust OV证书是一个备受推崇的选择。作为一家备受尊敬的数字证书颁发机构,GeoTrust以其卓越的品牌声誉和高质量的产品而闻名于世。GeoTrust OV证书提供了一系列的安全功能,同时还具有出色的性价比,…...

第一个“hello Android”程序
1、首先安装Android studio(跳过) Android Studio是由Google推出的官方集成开发环境(IDE),专门用于Android应用程序的开发。它是基于JetBrains的IntelliJ IDEA IDE构建的,提供了丰富的功能和工具࿰…...

docker-compose安装nacos和msql
docker-compose安装nacos和msql 前言前提已经安装docker-compose,如果没有安装,则可以查看上面系列文章中的安装教程。并且文章中使用的是mobaxterm连接虚拟机。 1、下载2、创建并运行 前言 前提已经安装docker-compose,如果没有安装&#x…...

AnythingLLM:基于RAG方案构专属私有知识库(开源|高效|可定制)
一、前言 继OpenAI和Google的产品发布会之后,大模型的能力进化速度之快令人惊叹,然而,对于很多个人和企业而言,为了数据安全不得不考虑私有化部署方案,从GPT-4发布以来,国内外的大模型就拉开了很明显的差距…...

常见的工作流编排引擎
常见工作流框架:微服务编排引擎 工作流框架还是比较多的,按照语言分类的话,有 Java: jBPM、Activiti、SWF PHP: Tpflow、PHPworkflow Go: Cadence(Cadence由Uber开发并开源,Maxim Fateev是Cadence的主架构师&#…...

期末总复习(重点!!!)
一、第6章异常处理 1、什么是异常、什么是异常处理异常是指程序在运行过程中发生的错误事件,影响程序的正常执行。异常并不是一定会发生,默认情况下,程序运行中遇到异常时将会终止,并在控制台打印出异常出现的堆栈信息。异常处理…...

input 获取焦点后样式的修改
一、实现目标 1.没有获取焦点时样子 2.获取焦点时 代码: <input class"input"placeholder"请输入关键字" input"loadNode" />css .input {border-radius: 14px;border:1px solid #e4e4e4;margin: 5px;margin-top: 10px;wi…...

持续集成交付CICD:Jenkins使用GitLab共享库实现自动上传前后端项目Nexus制品
目录 一、实验 1.GitLab本地导入前后端项目 2.Jenkins新建前后端项目流水线 3.Sonarqube录入质量阈与质量配置 4.修改GitLab共享库代码 5.Jenkins手动构建前后端项目流水线 6.Nexus查看制品上传情况 7.优化代码获取RELEASE分支 8.优化Jenkins流水线项目名称 一、实验 …...

50mA、24V、超低 IQ、低压降稳压器
一、Description The TPS715 low-dropout (LDO) voltage regulators offer the benefits of high input voltage, low-dropout voltage, low-power operation, and miniaturized packaging. The devices, which operate over an input range of 2.5 V to 24 V, are stable wit…...

【Python测试开发】文件上传操作
先写一个上传页面 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>文件上传</title><link href"http://dcn.bootcss/bootstrap/3.3.0/css/bootstrap.min.css" rel"styleshee…...

深兰科技AI医疗健康产品获3000台采购订单
12月6日,武汉某企业与深兰科技签署协议,一次性采购3,000台深兰科技AI生理健康检测仪——扁鹊。 深兰科技AI生理健康检测仪——扁鹊是深兰科技推出的人体生理指标检测产品。基于AI生物技术、融合互联网医疗及AIoT技术,深兰科技AI生理健康检测仪…...

金鸣表格文字识别的图片转word,模块不同,效果有何差异?
金鸣表格文字识别系统可以将图片等格式的文件转为word,而且有好几种输出word的方式,那么,它们都有什么区别呢? 一、表格识别模块输出的word。可以输出文本和表格混合格式的word,比较适合有表格样式的图片转换识别&…...

Qt Creator设置IDE的字体、颜色、主题样式
Qt是一款开源的、跨平台的C开发框架,支持Windows、Linux、Mac系统,从1995发布第一版以来,发展迅猛,最开始是用于Nokia手机的Symbian(塞班)系统和应用程序开发,现在是用于嵌入式软件、桌面软件(比如WPS、VirtualBox)、A…...

SpringBootWeb入门、HTTP协议、Web服务器-Tomcat
目录 一、SpringBootWeb入门 二、HTTP协议 HTTP-请求协议 HTTP-响应协议 HTTP-协议解析 三、Web服务器-Tomcat 服务器概述 Tomcat 一、SpringBootWeb入门 直接基于SpringFramework进行开发,存在两个问题:配置繁琐、入门难度大 通过springboot就…...

【Jenkins】Centos环境安装Jenkins(通过rpm安装)
在Centos操作系统中通过rpm安装Jenkins 参考官网 https://www.jenkins.io/doc/book/installing/linux/#red-hat-centos 1、下载安装Jdk17 下载安装 # 更新您的系统,不一定需要 # sudo yum -y update # 安装将用于下载 Java 17 二进制文件的 wget 命令行工具。 s…...

华为数通---配置基本QinQ示例
QinQ简介 定义 QinQ(802.1Q-in-802.1Q)技术是一项扩展VLAN空间的技术,通过在802.1Q标签报文的基础上再增加一层802.1Q的Tag来达到扩展VLAN空间的功能,可以使私网VLAN透传公网。由于在骨干网中传递的报文有两层802.1Q Tag&#x…...

利用poi实现将数据库表字段信息导出到word中
研发文档对于开发人员来说都不陌生了,而研发文档里重要的一部分就是表结构设计,需要我们在word建个表格把我们数据库中的表字段信息填进去,表多的话靠我们手动去填非常累人!!! 因此作为开发人员可不可以写…...

深入浅出分析kafka客户端程序设计 ----- 生产者篇----万字总结
前面在深入理解kafka中提到的只是理论上的设计原理, 本篇讲得是基于c语言的kafka库的程序编写!!!!! 首先要编写生产者的代码,得先知道生产者的逻辑在代码上是怎么体现的 1.kafka生产者的逻辑 …...

粗到细语义(Coarse-to-Fine Semantics)
粗到细语义(Coarse-to-Fine Semantics)是一种深度学习模型的设计方法,它通过逐步细化的方式来理解文本中的语义信息。这种方法通常用于文本分类、情感分析、问答等任务中。 在粗到细语义中,模型首先从整体上理解文本的大致意思&a…...

小程序开发实战案例四 | 小程序标题栏如何设置
上一期我们了解了 小程序底部导航栏 的实现效果,今天一起来了解下如何设置小程序标题栏~ 基础标题栏 小程序标题栏主要包含返回、标题、收藏、菜单、收起 5 个模块,其中能够调整的部分只有标题和背景色。 另外 IDE上无法展示收藏按钮&#…...

Flutter在Visual Studio Code上首次创建运行应用
一、创建Flutter应用 1、前提条件 安装Visual Studio Code并配置好运行环境 2、开始创建Flutter应用 1)、打开Visual Studio Code 2)、打开 View > Command Palette。 3)、在搜索框中输入“flutter”,弹出内容如下图所示,选择“ Flutter: New Pr…...

如何用ChatGPT分析恶意软件?
自从我们进入数字化时代以来,恶意软件就一直是计算机应用系统的“心腹大患”。事实上,每一次技术进步都会为恶意行为者提供更多的工具,使得他们的攻击行为更具破坏性。不过,如今生成式人工智能的崛起,似乎让一直以来的…...

【Axure高保真原型】能增删改的树形表格
今天和大家分享能增删改的树形表格的原型模板,包括展开、折叠、增加、修改、删除表格内容,那这个原型模板是通过中继器制作的,所以使用简单,只需要填写中继器表格,即可自动生成对应的树形表格。这个模板最高支持6级树形…...

前端打包工具之Webpack5
前端打包工具之Webpack5 什么是打包工具打包工具的作用常见的打包工具一、Webpack1、什么是[webpack](https://webpack.docschina.org/concepts/)2、webpack本身的功能是有限的3、webpack基本使用:基于本身功能只解析JS资源4、webpack配置4.1、entry(入口…...

linux设置环境变量
linux设置环境变量 大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! Linux设置环境变量:打造个性化开发环境 在Linux系统中,环境变量是一项…...

vue中对pdf文件和路径的处理
根据url预览pdf文件 地址栏输入url可以直接预览的pdf,这种我们可以直接使用vue-pdf进行预览 <div class"animation-box-pdf"><pdf :src"url" /></div><script> import Pdf from vue-pdfexport default {components: …...

Socks5与代理IP技术探析:构建安全高效的网络通信
1. Socks5协议的技术内幕 1.1 握手与身份验证 Socks5协议的握手阶段通过版本协商和灵活的身份验证方式建立安全连接。这确保了通信的可靠性和用户身份的安全。 1.2 数据传输机制 Socks5通过代理实现数据传输,支持TCP和UDP协议,为用户提供了高度灵活的…...

【lesson13】MySQL表的基本操作之create(创建),update(更新)和replace(替换)
文章目录 表的增删查改create测试建表基础测试 update测试建表基础测试 replace(替换)测试建表基础测试 表的增删查改 CRUD : Create(创建), Retrieve(读取),Update(更新),Delete(删除) create 测试 建表…...

SQL进阶 | HAVING子句
概述 “HAVING”其用法和含义与“WHERE”关键词相似,但具有更高级别的限定性。在SELECT语句中,“HAVING”关键词用于过滤聚合函数的结果。与“WHERE”关键词不同的是,“HAVING”关键词不能用于过滤单个行,它主要用于过滤由GROUP B…...