推荐教材:董付国著,《Python数据分析与数据可视化(微课版)》,ISBN:978-7-302-62420-2,清华大学出版社,2023年6月出版,2023年8月第2次印刷
配套资源:教学大纲、课件、源码、数据文件、34小时微课
- 《Python数据分析与数据可视化》教材插图彩图
- 《Python数据分析与数据可视化》教学大纲
========================
问题描述:
给定包含若干整数的任意列表,查找其中的最长非递减子序列。例如,[7, 1, 2, 5, 3, 4, 0, 6, 2]的最长非递减子序列为[1, 2, 3, 4, 6]。
参考代码:
运行结果如下,从长度35的列表中查找长度为10的最长非递减子序列时,最笨的暴力穷举算法用时18751秒,后面几个算法从不同的角度进行改进和优化,最后一种算法瞬间解决问题,算法至少有千万倍的速度提升。
为了进一步测试改进算法的效率,把原始数据改为长度1350的随机列表,专门测试func6(),把测试代码修改为:
运行结果如下,这样的问题规模前面几个函数尤其是前两个函数的运行时间之长恐怕是超出想象的,但func6()仍能在0.3秒钟给出结果。
继续修改测试代码,把测试数据改为长度3000的随机列表,重新运行程序,
运行结果:
=================
温馨提示:
公众号“Python小屋”