当前位置: 首页 > news >正文

算法竞赛——02基本算法

第二章-基本算法目录

  • 2.1-算法复杂度
    • 2.1.1-算法的概念
    • 2.1.2-复杂度和大O记号
  • 2.2-尺取法
    • 2.2.1-尺取法的概念
    • 2.2.2-反向扫描
    • 2.2.3-同向扫描 ---> 未完待续 20241031
  • 2.3-二分法
  • 2.4-三分法
  • 2.5-倍增法与ST算法(中级难度)
  • 2.6-前缀和与查分(中级难度)
  • 2.7-离散化(中级难度)
  • 2.8-排序与排列
  • 2.9-分治法(中级难度)
  • 2.10-贪心法与拟阵(中级难度)

2.1-算法复杂度

  计算的资源是有限的,竞赛题会限制代码所使用的计算资源。计算资源有两种:计算时间存储空间。与此对应的有时间复杂度空间复杂度,时间复杂度衡量计算的次数,空间复杂度衡量需要的存储空间
  算法竞赛的题目,都会对代码的运行时间和空间做出要求。一般情况下,C++代码的运行时间是1秒,即代码必须在1秒内计算结果并输出结果;空间一般不超过100MB。如果是Java和Python代码,运行时间应该是C++代码的3~5倍。

  需要说明的是,时间复杂度不完全等于运行时间。由于代码的运行时间依赖于计算机的性能,同样的代码在不同的机器上运行,需要的时间不同。所以,直接把运行时间作为判断标准并不准确。用代码执行的次数衡量更加合理,如一个for循环了n次,把它的时间复杂度记为 O ( n ) O(n) O(n)

2.1.1-算法的概念

  一般认为:“程序 = 算法 + 数据结构”算法是解决问题的逻辑、方法、步骤,数据结构是数据在计算机中的存储和访问的方式。算法和数据结构是紧密结合的,而且有些数据结构有特定的处理方法,此时很难把数据结构和算法区分开来。

  算法(Algorithm)是对特定问题求解步骤的一种描述,是指令的有限序列。算法有以下5个特征。
   ( 1 ) (1) (1)输入:一个算法有零个或多个输入。算法可以没有输入,如一个定时闹钟程序,它不需要输入,但是通过每隔一段时间就输出一个报警。
   ( 2 ) (2) (2)输出:一个算法有一个或多个输出。程序可以没有输入,但是一定要有输出。
   ( 3 ) (3) (3)有穷性:一个算法必须在执行有穷步之后结束,且每步都在有穷时间内完成。
   ( 4 ) (4) (4)确定性:算法中的每条指令必须有确切的含义,对于相同的输入只能得到相同的输出。
   ( 5 ) (5) (5)可行性:算法描述的操作必须通过已经实现的基本操作执行有限次来实现。
  以冒泡排序算法为例,它满足上述5个特征,具体如下。
   ( 1 ) (1) (1)输入:由n个数构成的序列 { a 1 , a 2 , a 3 , ⋅ ⋅ ⋅ , a n } \{a_1, a_2, a_3, ···, a_n\} {a1,a2,a3,⋅⋅⋅,an}
   ( 2 ) (2) (2)输出:对输入的排序结果 { a 1 ′ , a 2 ′ , a 3 ′ , ⋅ ⋅ ⋅ , a n ′ } , a 1 ′ ≤ a 2 ′ ≤ a 3 ′ ≤ , ⋅ ⋅ ⋅ , ≤ a n ′ \{a_1^{'}, a_2^{'}, a_3^{'}, ···, a_n^{'}\}, a_1^{'} \le a_2^{'} \le a_3^{'} \le, ···, \le a_n^{'} {a1,a2,a3,⋅⋅⋅,an},a1a2a3,⋅⋅⋅,an
   ( 3 ) (3) (3)有穷性:算法在执行 O ( n 2 ) O(n^2) O(n2)次后结束,这也是对算法性能的评估,即算法复杂度。
   ( 4 ) (4) (4)确定性:算法的每个步骤都是确定的。
   ( 5 ) (5) (5)可行性:算法的步骤能编程实现。

2.1.2-复杂度和大O记号

  衡量算法性能的主要对象是时间复杂度,一般不讨论空间复杂度。因为一个算法的空间复杂度是容易分析的,而时间复杂度往往关系到算法的根本逻辑


http://www.mrgr.cn/news/62713.html

相关文章:

  • 净水前置需要安装吗?
  • Python实现深度学习模型预测控制(tensorflow)DL-MPC(Deep Learning Model Predictive Control
  • 什么是x86架构,什么是arm架构
  • Github 2024-10-24 Go开源项目日报 Top10
  • 多GPU训练大语言模型,DDP, ZeRO 和 FSDP
  • C#实现视频会议录制(支持Windows、Linux、银河麒麟、统信UOS)
  • AI机西好用吗?有哪些实用功能?真实用户体验告诉你!
  • 网鼎杯2024青龙组官方资格赛wp
  • 接入AI后,开源项目顿时有趣了
  • JVM(HotSpot):finally块的相关问题
  • CSS网页布局综合练习(涵盖大多CSS知识点)
  • 台州ctf市赛reverse(easy_choice)超详细复现
  • 什么是决策树桩
  • 因特网的概述和三种交换方式
  • C++笔记---可变参数模板
  • XHCI 1.2b 规范摘要(八)
  • 从零实现数据结构:二叉搜索树
  • 【HTML5标准】深度解析HTML5:前端开发的基石
  • 【深度学习】VITS语音合成原理解析
  • 向量库Milvus异常挂了,重新启动
  • 有没有优质的公司可以提供高质量大模型数据?
  • Vue.js(2) 基础:指令与功能概览
  • C++对象模型:Function 语意学
  • 九泰智库 | 医械周刊- Vol.65 | 广州发布首批创新药械产品目录
  • 【产品经理】工业互联网企业上市之路
  • 【2024.10.31练习】123