Python中文
首页
教程
问答
标签
搜索
登录
注册
通过将列表转换为集合并返回到列表来排序列表的时间复杂性
回答此问题可获得
20
贡献值,回答如果被采纳可获得
50
分。
<p>我最近看了<a href="https://www.youtube.com/watch?v=p33CVV29OG8" rel="nofollow noreferrer">Raymond Hettingers talk about python dictionaries</a>(以及扩展集…),他提到整数散列到自身,向dict(或集…)添加整数将按顺序插入它们,只要不删除项,顺序将保留在Python3.6(可能更高?)中。在对<a href="https://stackoverflow.com/questions/39980323/are-dictionaries-ordered-in-python-3-6">this question</a>的回答中指出,字典保留插入顺序,但对于集合,它像整数一样根据其值排序</p> <p>现在:根据<a href="https://wiki.python.org/moin/TimeComplexity" rel="nofollow noreferrer">time-complexity section of python.org</a>和更详细的<a href="https://www.geeksforgeeks.org/internal-working-of-set-in-python/" rel="nofollow noreferrer">here</a>,说明向集合添加元素的平均时间复杂度为O(1)。这意味着,如果您有一个未排序的整数列表,则只需执行以下操作即可对其进行排序:</p> <pre><code>sorted_list = list(set(unsorted_list)) </code></pre> <p>就我所测试的情况而言,这是事实(用随机序列做了1000次)</p> <p>我现在的问题是:这是否意味着可以在O(n)时间内对python中的整数进行排序</p> <p>对我来说是这样的,因为构建集合需要O(n),将集合转换回列表需要O(n),还是我在这里遗漏了什么</p>
0 条评论
分类:
Python问答
请先
登录
后评论
默认排序
时间排序
1 个回答
匿名
1天前
擅长:python、mysql、java
<p>不,不是一般的。您一定在特殊情况下尝试过,例如,未排序的输入列表包含从0到n的所有数字,每次一次</p> <p>以下是一个失败的简单案例:</p> <pre><code>>>> list(set([8, 1])) [8, 1] </code></pre> <p>使用CPython 3.8.1 32位完成</p>
请先
登录
后评论
针对此问题:
更多的回答
关注
89
关注
收藏
1
收藏,
216
浏览
网友 提问于 2天前
相关Python问题
无法使用Django/mongoengine连接到MongoDB(身份验证失败)
6 回答
无法使用Django\u mssql\u后端迁移到外部hos
5 回答
无法使用Django&Python3.4连接到MySql
5 回答
无法使用Django+nginx上载媒体文件
10 回答
无法使用Django1.6导入名称模式
5 回答
无法使用Django1.7和mongodb登录管理站点
5 回答
无法使用Djangoadmin创建项目,进程使用了错误的路径,因为我事先安装了错误的Python
1 回答
无法使用Djangockedi验证CBV中的字段
2 回答
无法使用Djangocketditor上载图像(错误400)
8 回答
无法使用Djangocron进行函数调用
1 回答
无法使用Djangofiler djang上载文件
2 回答
无法使用Djangokronos
9 回答
无法使用Djangomssql provid
2 回答
无法使用Djangomssql连接到带有Django 1.11的MS SQL Server 2016
4 回答
无法使用Djangomssq迁移Django数据库
3 回答
无法使用Djangonox创建用户
9 回答
无法使用Djangopyodb从Django查询SQL Server
7 回答
无法使用Djangopython3ldap连接到ldap
3 回答
无法使用Djangoredis连接到redis
4 回答
无法使用Django中的FK创建新表
3 回答