社区所有版块导航
Python
python开源   Django   Python   DjangoApp   pycharm  
DATA
docker   Elasticsearch  
aigc
aigc   chatgpt  
WEB开发
linux   MongoDB   Redis   DATABASE   NGINX   其他Web框架   web工具   zookeeper   tornado   NoSql   Bootstrap   js   peewee   Git   bottle   IE   MQ   Jquery  
机器学习
机器学习算法  
Python88.com
反馈   公告   社区推广  
产品
短视频  
印度
印度  
Py学习  »  Python

Python字符串迭代的时间复杂性

Learning stats by example • 6 年前 • 2638 次点击  

Python的时间复杂度是多少? for in 带字符串的迭代构造?

例如。,

for s in 'test:
   ... # s = t, e, s, t

循环的总运行时间是多少?

编辑:我看到我混淆了Python的字符串片段查找和索引查找。它的索引查找是O(1),因此总循环应该是O(n),与列表相同。

Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/52709
文章 [ 2 ]  |  最新文章 6 年前
Heap Overflow
Reply   •   1 楼
Heap Overflow    6 年前

它是O(n),但是索引查找参数是一个红鲱鱼。

如果这样做,索引查找速度将很重要:

for index in range(len(mystring)):
    char = mystring[index]
    ...

但你是 不 使用索引。你用的是 迭代器 ,更确切地说是 一串 迭代器:

>>> iter('test')
<str_iterator object at 0x03569820>

迭代器会记住它在字符串中的位置(不管它喜欢什么方式,都不需要是“索引”)。并且可以反复询问下一个字符:

>>> it = iter('test')
>>> next(it)
't'
>>> next(it)
'e'
>>> next(it)
's'
>>> next(it)
't'
>>> next(it)
Traceback (most recent call last):
  File "<pyshell#200>", line 1, in <module>
    next(it)
StopIteration

这就是 for -循环是的。它创建那个迭代器,然后重复地向它请求下一个值,直到迭代器告诉它停止为止。它从迭代器获得的每一个值,都会在您命名的变量中赋予您的代码。换句话说 对于 -循环实际上只是迭代器和循环体中的代码之间的中间人。

与字符串相反,想象一个简单的链表。链表中的索引查找采用O(n),因为每次查找都需要从链表的开头走到所需的节点。但是您仍然可以很容易地在O(n)中进行完整的迭代,对吗?迭代器对象将保留对下一个节点的引用,因此它将在O(1)时间内提供它(然后向前移动它的引用)。所以对于链表来说 对于 -使用索引的循环将花费O(n 2个 )但是正常的蟒蛇 对于 -循环(隐式使用链表迭代器)将是O(n)。

你甚至可以模仿 对于 -用一个 while -循环和显式迭代器由您自己处理,而不是让 对于 -循环处理它给你。而不是

for char in 'test':
    print(char)

执行以下操作:

it = iter('test')
while True:
    try:
        char = next(it)
    except StopIteration:
        break
    print(char)

上面印着:

t
e
s
t
Nimesha Dilini
Reply   •   2 楼
Nimesha Dilini    6 年前

答案是O(n)。 查看本网站了解更多关于时间复杂度的信息 python time complexity