8wDlpd.png
8wDFp9.png
8wDEOx.png
8wDMfH.png
8wDKte.png

比较两个 Python 列表的复杂度顺序是什么?

Spencer Pollock 2月前

43 0

假设列表仅包含可哈希对象。

假设列表仅包含可哈希对象。

帖子版权声明 1、本帖标题:比较两个 Python 列表的复杂度顺序是什么?
    本站网址:http://xjnalaquan.com/
2、本网站的资源部分来源于网络,如有侵权,请联系站长进行删除处理。
3、会员发帖仅代表会员个人观点,并不代表本站赞同其观点和对其真实性负责。
4、本站一律禁止以任何方式发布或转载任何违法的相关信息,访客发现请向站长举报
5、站长邮箱:yeweds@126.com 除非注明,本帖由Spencer Pollock在本站《algorithm》版块原创发布, 转载请注明出处!
最新回复 (0)
  • 如果两个列表的长度均为 n,则比较两个列表的复杂度为 O(n);如果列表的长度不同,则比较两个列表的复杂度为 O(1)。

  • Allu 2月前 0 只看Ta
    引用 3

    这在很大程度上取决于‘比较’一词的含义。

    如果比较相等性,则@Sven-Marnach 的答案适用:长度相同时为 O(n),长度不同时为 O(1)。

    如果您要将多个列表相互比较,则使用哈希函数会有所帮助:对于不同的列表(具有不同的哈希值),其复杂度为 O(1),而对于具有相同哈希值的列表,其复杂度可能仍为 O(n),因为哈希值可能会发生冲突,您必须进行真正的比较。这可以通过使用多个哈希函数来缓解,因此发生冲突的概率会大大降低。

    请注意,计算长度为 n 的列表的哈希值仍然需要 O(n),因此这里没有免费午餐。

    如果您想比较两个列表的相似性,您可能需要 Levenshtein 距离 ,在简单的情况下,该距离是时间的二次方,但可以通过惰性求值变为线性,但可能会花费大量的内存。

    创建一个列表所需要做的完整更改列表 diff ,则在 Wikipedia 中提到的最佳实现中它是二次的。

  • O(n)。对于给定的算法选择,答案不可能是“视情况而定”。对于最坏的情况,答案始终是明确的。这就是为什么它(大 O 符号)被称为“渐近分析”。

返回
作者最近主题: