Python算法中的时间复杂度问题
作者：软件测试开发技术栈 发布时间：2021-03-20 04:52:50
在实现算法的时候，通常会从两方面考虑算法的复杂度，即时间复杂度和空间复杂度。顾名思义，时间复杂度用于度量算法的计算工作量，空间复杂度用于度量算法占用的内存空间。
本文将从时间复杂度的概念出发，结合实际代码示例分析算法的时间复杂度。
渐进时间复杂度
时间复杂度是算法运算所消耗的时间，因为不同大小的输入数据，算法处理所要消耗的时间是不同的，因此评估一个算运行时间是比较困难的，所以通常关注的是时间频度，即算法运行计算操作的次数，记为T(n)，其中n称为问题的规模。
同样，因为n是一个变量，n发生变化时，时间频度T(n) 也在发生变化，我们称时间复杂度的极限情形称为算法的渐近时间复杂度，记为O(n)，不包含函数的低阶和首项系数。
我们以如下 例子来解释一下：
如上例子中，我们根据代码上执行的平均时间假设，计算 run_time(n) 函数的时间复杂度，如下：
上述时间复杂度计算公式T(n) ，是我们对函数 run_time(n) 进行的时间复杂度的估算。当n 值非常大的时候，T(n)函数中常数项 time0 以及n的系数 (time1+time2+time3+time4) 对n的影响也可以忽略不计了，因此这里函数run_time(n) 的时间复杂度我们可以表示为 O(n)。
因为我们计算的是极限状态下(如，n非常大)的时间复杂度，因此其中存在以下两种特性：
低阶项相对于高阶项产生的影响很小，可以忽略不计。 最高项系数对最高项的影响也很小，可以忽略不计。
根据上述两种特性，时间复杂度的计算方法：
1.只取最高阶项，去掉低阶项。
2.去掉最高项的系数。
3.针对常数阶，取时间复杂度为O(1)。
我们通过下面例子理解一下常见的时间复杂度，如下：
时间复杂度：常数阶 O(1)
时间复杂度：线性阶 O(n)
时间复杂度：线性阶 O(n)
时间复杂度：平方阶 O(n^2)
时间复杂度：平方阶 O(n^2)
时间复杂度：平方阶 O(n^2)
时间复杂度：立方阶 O(n^3)
时间复杂度：对数阶 O(logn)
随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低，时间复杂度排序如下：
练习一下
如下count_sort 函数实现了计数排序，列表中的数范围都在0到100之间，列表长度大约为100万。
如上count_sort 函数的 空间复杂度为 O(n)，公式如下：
总结
以上所述是小编给大家介绍的Python算法中的时间复杂度问题网站的支持！
如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！
来源：https://developer.51cto.com/art/201911/606148.htm
0
投稿猜你喜欢
相信大家对python-docx这个常用的操作docx文档的库都不陌生，它支持以内联形状（Inline Shape）的形式插入图片，即图片和- 今天在开发的时候，项目报了一个警告 Duplicate named routes definition ，这里记录一下
- 使用场景批量合并相同格式的Exce，给DataFrame添加行，给DataFrame添加列使用说明：1.使用某种合并方式（inner/out
- 界面设计页面引用了youzan组件进行设计，包括icon,button,tag,toast以及布局github地址：https://gith
- 1. desc 命令 格式: desc tablename columnname 例子: desc `table` `mid` desc `
- 每次抽取后都重新洗牌。计算10000次随机抽取可得到同花的几率。我做的比较复杂，分别累计了四种花色分别出现了几次import randoml
- enum 是一组绑定到唯一常数值的符号名称，并且具备可迭代性和可比较性的特性。我们可以使用 enum 创建具有良好定义的标识符，而不是直接使
- 1. 引用css。这可能是最常见的做法了，对一些特定的元素定义特定的样式。那么使用它，你需要在HTML 页面中加入<link
- 在计算机普及的现代设计领域，文字的设计的工作很大一部分由计算机代替人脑完成了（很多平面设计软件中都有制作艺术汉字的引导，以及提供了数十上百种
- 导入同级模块导入sys，一定要将当前包所在路径添加进来。import syssys.path.append(r"directory
- 一.脚本基础1.USE语句设置当前数据库。2.声明变量语法：DECLARE @变量名 变量类型在声明变量后，给变量赋值之前，变量的值为NUL
- 本文介绍基于Python中gdal模块，实现对大量栅格图像批量绘制直方图的方法。首先，明确一下本文需要实现的需求：现需对多幅栅格数据文件进行
- 1、ModuleNotFoundError: No module named ‘scipy.spatial.transf
- 固定路由的面包屑导航我们在配置router的时候，可以将面包屑数据配置在meta中，例如路由配置：{ path: '/p
- 一、前言本文就从数据爬取、数据清洗、数据可视化，这三个方面入手，但你简单完成一个小型的数据分析项目，让你对知识能够有一个综合的运用。整个思路
- 前言我原本是学C\C++，这是本人第一篇关于python的文章。请多多关照！对于python为什么要打包成exe文件，是因为传输源文件以及源
- 初学OpenCV图像处理的小伙伴肯定对什么高斯函数、滤波处理、阈值二值化等特性非常头疼，这里给各位分享一个小项目，可通过摄像头实时动态查看各
- 框架概念框架和web服务器关系·静态资源：不是经常变化的资源、往往是固定不变的资源·动态资源：经常变化的资源·模板文件：提供了一个显示的模板
- 装饰器的基础使用（装饰带参函数）def decorator(func): def inner(info): &nb
- python3.7 打包成exe程序环境：pycharm2018.1+win7+python3.7工具：pyinstaller1、安装pyi
