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
Lsj777
V2EX  ›  Python

关于 Python 的时间复杂度

  •  
  •   Lsj777 · 2019-11-26 16:51:39 +08:00 · 2939 次点击
    这是一个创建于 1813 天前的主题,其中的信息可能已经有所发展或是发生改变。

    新手入坑,请各位大佬指点下时间复杂度该怎么去区分呢?

    比如 例子: a = [xxx,yyy,xxx] b = [yyy,xxx,yyy] c = set()

    for i in a:
    	c.add(i)
    
    for i in a:
    	c.add(i)
    sorted(c)
    

    以上例子的时间复杂度应该怎么计算呢?

    小白再次谢谢各位大神们的支援了~~~

    7 条回复    2019-11-26 17:03:25 +08:00
    lhx2008
        1
    lhx2008  
       2019-11-26 16:54:54 +08:00 via Android
    各个数据结构的各个操作的时间复杂度,python 有一篇文档直接告诉你了,你就算一下就好了
    Lsj777
        2
    Lsj777  
    OP
       2019-11-26 16:56:44 +08:00
    @lhx2008 谢谢大佬 不过我想问的是 比如在两个 for 循环之后 sorted,这种时间复杂度应该怎么计算出来呢?是 2n+n*log(n) 吗?
    lhx2008
        3
    lhx2008  
       2019-11-26 16:57:16 +08:00 via Android
    当然,dict/set 类型 和 list 因为数据结构不同,对于同一个操作复杂度是有差异的,但是这两个大类的复杂度和教科书以及和大多数其他语言都是相同的
    lhx2008
        4
    lhx2008  
       2019-11-26 16:58:13 +08:00 via Android
    @Lsj777 你写的这个可以理解为执行了多少次,但是不是大 O 时间复杂度
    Lsj777
        5
    Lsj777  
    OP
       2019-11-26 17:00:58 +08:00
    @lhx2008 那正确的时间复杂度应该是多少呢? O(n*log(n))吗?
    lhx2008
        6
    lhx2008  
       2019-11-26 17:01:47 +08:00 via Android
    通常来说,你这整个时间复杂度是 O(nlogn) n=len(a)+len(b)
    Lsj777
        7
    Lsj777  
    OP
       2019-11-26 17:03:25 +08:00
    @lhx2008 谢谢大佬的帮助~
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1060 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 20:04 · PVG 04:04 · LAX 12:04 · JFK 15:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.