问题描述
感谢您的帮助
words = [....#Big list of words]
words_set = set(words)
当n = len(words)时,我很难确定set(words)的复杂度.是O(n)因为它在列表的所有项目上移动,还是O(l(n-l))(当l是单个单词长度时)?感谢帮助!如果WC和BC之间也有区别.
I have hard time determine what is the complexity of set(words) when n=len(words).Is it O(n) since it moves on all the items of the list, or O(l(n-l)) when l is a single word length?Thanks for help! If there is a difference between WC and BC too.
不要介意O(l(n-l)),这是重复子字符串大O的错误.
don't mind O(l(n-l)) it's mistake for repeating substring big O.
推荐答案
我不理解您的第二个选择,但是迭代一个列表是O(n),您必须迭代该列表才能将其转换为集合.每个元素上的任何操作(例如哈希)都是一个常数因子,由线性迭代时间决定.
I don't understand your second option, but iterating a list is O(n) and you must iterate the list to convert it to a set. Any operation on each element - eg hashing - is a constant factor which is dominated by the linear time of iteration.
这篇关于Python将列表转换为集合,大O的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!