推荐学习书目 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
这是一个创建于 2693 天前的主题，其中的信息可能已经有所发展或是发生改变。
AList = [1,2,3]
BSet = {1,2,3}
问：
- 从 AList 和 BSet 中查找 4，最坏时间复杂度哪个大？
- 从 AList 和 BSet 中插入 4，最坏时间复杂度哪个大？
 | 1 swulling 201-06-01 19:03:15 +08:00 via iPhone A A |
 | 2 clino 2018-06-01 19:12:07 +08:00 via Android set 没有插入概念吧，应该说加入 |
 | 3 lniwn 2018-06-01 19:28:24 +08:00 |
 | 4 enenaaa 2018-06-01 19:51:51 +08:00 弄清楚列表和哈希表的区别就好了。 1. 对于查找， 列表时间复杂度是 O(n)，set 是 O(1)。 所以列表的时间复杂度更大。 2. 对于插入， 两个都是 O(1) |
 | 5 fuchaofather 2018-06-01 20:02:41 +08:00 via Android 楼主描述不太清楚啊。一般是顺序结构跟链式比较复杂度。很少线性表跟哈希表比较复杂度啊。正常来说值比较线性表复杂度是 On，哈希是 O1。看你提供的是有序顺序结构，看数据量决定要不要建索引。复杂度都是可以优化的，比如顺序结构折半查找可以实现 lgn |
| 6 fuchaofather 2018-06-01 20:03:39 +08:00 via Android 还有线性表插入顺序结构首尾插入效率又不一样，哈希表示哈希后 put |
 | 7 suber 2018-06-01 20:05:23 +08:00 最坏时间复杂度，应该要考虑哈希出现碰撞，而 Python 的实现是开放寻址。不确定 set 最坏复杂度是不是 O(n) |
 | 8 smallQ OP 这是今天群里面看到的一道面试题，， |
 | 9 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) |
 | 11 Jayce245 2018-06-07 09:08:52 +08:00 set 是 o(1 ）啊，当然比 list O(n)快 |
Select Language