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

算法第二章作业

找第 k 小的数的分治算法自然语言描述:
找第 k 小的数的分治算法,首先要选择一个基准元素,然后将数组分成两部分,一部分是小于等于基准元素的数,另一部分是大于基准元素的数。假设基准元素在划分后位于数组的第 m 个位置(从 1 开始计数)。如果 m 等于 k,那么基准元素就是第 k 小的数;如果 m 大于 k,说明第 k 小的数在小于等于基准元素的那部分子数组中,递归地在该子数组中找第 k 小的数;如果 m 小于 k,说明第 k 小的数在大于基准元素的那部分子数组中,递归地在该子数组中找第 (k - m) 小的数。

最好时间复杂度:
最好的情况是每次划分都能将数组分成大致相等的两部分。此时,算法的时间复杂度可以用递推式
T(n)=T( 2/n)+O(n)来表示。根据主定理,这种情况下时间复杂度为 O(n)。因为每次都能快速缩小问题规模,只需要线性时间就能找到第 k 小的数。
最坏时间复杂度:
最坏的情况是每次划分都将数组分成极不均匀的两部分,比如每次都把最小的元素作为基准,此时问题规模每次只减少 1。递推公式为 T(n)=T(n−1)+O(n)。展开这个递推式T(n)=O(n)+O(n−1)+⋯+O(1)=O(nn ),所以最坏时间复杂度是 O(nn)。

对分治法的体会和思考
分治法的核心思想是 “分而治之”,将一个复杂的大问题分解成若干个结构相似、规模较小的子问题,分别解决子问题后,再将子问题的解合并得到原问题的解。这种思想在很多算法中都有体现,比如快速排序、归并排序等。在找第 k 小的数的问题中,分治法通过划分操作,把找第 k 小的数的问题转化为在子数组中找更小数的问题,大大简化了问题的求解过程。分治法的优势在于,当子问题的规模足够小时,解决子问题的成本很低,而且如果能均匀地划分问题,往往能得到很好的时间复杂度.但分治法也有不足,就像快速选择算法的最坏情况,当划分不均匀时,时间复杂度会退化,这也提醒我们在使用分治法时,划分策略的选择非常关键,好的划分能让算法效率大幅提升,而差的划分可能导致算法性能不佳。此外,分治法体现了一种解决问题的策略思维,把大困难拆解成小麻烦,逐个击破,这种思维不仅在算法设计中有用,在实际生活中解决复杂问题时也很有启发意义。

http://www.hskmm.com/?act=detail&tid=34604

相关文章:

  • 102302148谢文杰第一次数据采集作业
  • RaspberryPi 个人服务搭建
  • tryhackme-预安全-网络如何工作-网站如何工作-11
  • 2025塑料托盘优质厂家推荐,力森塑业科技多元化产品满足各类需求!
  • 嵌入式实验3串口通信--任务二USART1通信
  • Drive Snapshot
  • 20232319 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • 刷题日记—洛谷循环题单
  • 为什么需要学习变异的算法?
  • 今天搞了新的回归,不显著
  • shell编程学习笔记005之until循环
  • shell编程学习笔记006之select循环
  • burpsuite抓取小程序公众号数据包-cnblog
  • 2026 NOI 做题记录(七)
  • esp8266模块开发准备工作
  • 关于本学期我的编码规范与数学之美第一章观后感 - C
  • 线程--线程生命周期、Synchronized
  • C#中Yolo开发环境
  • CF1918F Caterpillar on a Tree
  • tryhackme-预安全-网络如何工作-DNS 详细信息-09
  • Diffusion
  • SP4191 天空代码 分析
  • l2正则化项以及torch.norm
  • 又数据结构
  • 大物实验
  • 蒙特卡洛保形预测技术解析
  • [KaibaMath]1013 关于收敛数列保不等式性的证明
  • 20231408徐钰涵《密码系统设计》
  • 洛谷比赛做题记录
  • 什么是命运(摘抄)