CH2_算法性能分析_找出第k小的元素
2021/11/12 22:11:36
本文主要是介绍CH2_算法性能分析_找出第k小的元素,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题描述:
(必做)给定一个乱序数字列表,编写一个算法复杂度是 O(nlogn)的算法,找出第k小的元素;
(选做)针对该问题,能将算法的时间复杂度优化到线性阶?请说明思路!
要求:(1)编写程序,能够打印数字列表和第k小的元素,给出程序以及输出截图
(2)算法复杂度可以借助画图/表格/文字等形式表现,必须要有自己的分析
我的答案:
查询了一些排序算法的比较,具体可以参考这篇,写得很详细。各种排序算法复杂度比较_zhc_24的博客-CSDN博客_排序算法复杂度
最后选择研究归并排序,先分割再集成,将所有数据用递归的方式排成递归树,每层最多进行n次比较,一共最多logn层,时间复杂度为O(nlogn)。
def merge(arr, l, m, r): n1 = m - l + 1 n2 = r - m L = [0] * (n1) # 临时数组L和R R = [0] * (n2) for i in range(0, n1): # 拷贝数据 L[i] = arr[l + i] for j in range(0, n2): R[j] = arr[m + 1 + j] i, j, k = 0, 0, l # 初始化索引 while i < n1 and j < n2: # 排序 if L[i] <= R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 # 拷贝保留元素 while i < n1: arr[k] = L[i] i += 1 k += 1 while j < n2: arr[k] = R[j] j += 1 k += 1 def mergeSort(arr, l, r): if l < r: m = int((l + (r - 1)) / 2) mergeSort(arr, l, m) mergeSort(arr, m + 1, r) merge(arr, l, m, r)
主函数部分:
def main(): arr = list(map(int, input("输入一组数,要求以空格隔开:").split(' '))) k = int(input("输出第k小的数,其中k的值为:")) n = len(arr) print("\n\n给定的数组为:", arr) mergeSort(arr, 0, n - 1) print("排序后的数组", arr) print("其中第k小的数为:", arr[k - 1]) main()
部分代码参考了这里的Python 归并排序 | 菜鸟教程 (runoob.com) ,有图解,比较容易理解。
(放一个交作业时候的输出示例:
over。
这篇关于CH2_算法性能分析_找出第k小的元素的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升