我指的是这个:http://docs.python.org/tutorial/datastructures.html
根据大O符号,list.index(x)
函数的运行时间是多少?
发布于 2011-05-07 12:25:09
对于线性搜索(例如,list.index),任何列表实现都将具有O(n)复杂度。尽管可能有一些古怪的实现做得更糟……
您可以通过使用不同的数据结构来提高查找的复杂性,例如有序列表或集合。这些通常是用二叉树实现的。然而,这些数据结构对它们所包含的元素施加了约束。在二叉树的情况下,元素需要是可排序的,但查找成本降至O(log )。
如前所述,在这里查找标准Python数据结构的运行时成本:http://wiki.python.org/moin/TimeComplexity
发布于 2019-05-22 13:23:13
使用以下代码检查计时。其复杂度为O(n)。
import time
class TimeChecker:
def __init__(self, name):
self.name = name
def __enter__(self):
self.start = self.get_time_in_sec()
return self
def __exit__(self, exc_type, exc_val, exc_tb):
now = self.get_time_in_sec()
time_taken = now - self.start # in seconds
print("Time Taken by " + self.name + ": " + str(time_taken))
def get_time_in_sec(self):
return int(round(time.time() * 1000))
def test_list_index_func(range_num):
lis = [1,2,3,4,5]
with TimeChecker('Process 1') as tim:
for i in range(range_num):
lis.index(4)
test_list_index_func(1000)
test_list_index_func(10000)
test_list_index_func(100000)
test_list_index_func(1000000)
print("Time: O(n)")
发布于 2018-10-15 06:52:27
上面提供的文档不包括list.index()
据我所知,list.index是O(1)运算。如果你想了解更多,这里有一个链接。https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt
https://stackoverflow.com/questions/5913671
复制相似问题