虽然我对它不陌生,但我并不经常使用Python,我的知识面比较广泛,而且对这门语言的了解也不是很深入。也许在这里有更加熟悉的人可以回答我的问题。我发现自己需要将项目添加到列表中,并保持项目添加时的排序。一种快速的方法是:
list.append(item) // O(1)
list.sort() // ??
我想如果这是向列表添加项的唯一方法,我希望排序会相当高效,因为在每次添加时都会对列表进行排序。但是还有另一种方法也可以实现同样的功能:
inserted = False
for i in range(len(list)): // O(N)
if (item < list[i]):
list.insert(i, item) // ??
inserted = True
break
if not inserted: list.append(item)
有人能告诉我哪个更有效率吗?虽然我倾向于第二组语句,但实际上我并不确定。
.insert()
的时间复杂度为O(N),而.sort()
的时间复杂度为O(N log N)。 - Wooble.sort()
的时间复杂度是O(N),因为除了新项之外,列表已经排序好了。 - John La Rooy