遇到一个 list 和 set 时间复杂度的问题，哪个老哥帮忙解答下

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

这是一个创建于 2402 天前的主题，其中的信息可能已经有所发展或是发生改变。

AList = [1,2,3]
BSet = {1,2,3}

问：

从 AList 和 BSet 中查找 4，最坏时间复杂度哪个大？
从 AList 和 BSet 中插入 4，最坏时间复杂度哪个大？

aList

bset

复杂

老哥

11 条回复 • 2018-06-07 09:08:52 +08:00

swulling

2018-06-01 19:03:15 +08:00 via iPhone

A
A

clino

2018-06-01 19:12:07 +08:00 via Android

set 没有插入概念吧，应该说加入

lniwn

2018-06-01 19:28:24 +08:00

看图 https://i.loli.net/2018/06/01/5b112d2fbfb22.png

enenaaa

2018-06-01 19:51:51 +08:00

弄清楚列表和哈希表的区别就好了。
1. 对于查找，列表时间复杂度是 O(n)，set 是 O(1)。所以列表的时间复杂度更大。
2. 对于插入，两个都是 O(1)

fuchaofather

2018-06-01 20:02:41 +08:00 via Android

楼主描述不太清楚啊。一般是顺序结构跟链式比较复杂度。很少线性表跟哈希表比较复杂度啊。正常来说值比较线性表复杂度是 On，哈希是 O1。看你提供的是有序顺序结构，看数据量决定要不要建索引。复杂度都是可以优化的，比如顺序结构折半查找可以实现 lgn

fuchaofather

2018-06-01 20:03:39 +08:00 via Android

还有线性表插入顺序结构首尾插入效率又不一样，哈希表示哈希后 put

suber

2018-06-01 20:05:23 +08:00

最坏时间复杂度，应该要考虑哈希出现碰撞，而 Python 的实现是开放寻址。不确定 set 最坏复杂度是不是 O(n)

smallQ

2018-06-01 21:06:43 +08:00

这是今天群里面看到的一道面试题，，

tkmiles

2018-06-02 10:26:20 +08:00

看看源码就知道了

list 是数组, append 是 O(1), 而 insert 因为要把元素往后移, 所以最坏是 O(n), 比如 insert(0, x)

set 是哈希表, 基本上加入只是求 hash 位置, 基本上是 O(1), 更细节一点的话, set 的 hash 寻址是二次散列和顺序寻址结合的, 不过基本上也可以看成算是 O(1)

smallQ

2018-06-03 14:31:45 +08:00

@tkmiles tks

Jayce245

2018-06-07 09:08:52 +08:00

set 是 o(1 ）啊，当然比 list O(n)快