Big O 表示法用于按字母顺序对嵌套列表理解中的每个元素进行排序

分享于2022年07月17日 algorithm big-o python sorting 问答
【问题标题】:Big O 表示法用于按字母顺序对嵌套列表理解中的每个元素进行排序(What would the Big O notation be for alphabetically sorting each element in a nested list comprehension)
【发布时间】:2022-01-28 01:00:36
【问题描述】:
# find all possible sorted substrings of s
substr = ["".join(sorted(s[i: j])) 
                for i in range(len(s)) 
                    for j in range(i + 1, len(s) + 1)]

我知道 sorted() 方法是 O(nlog(n)),所有可能的子串的查找是 O(n^2)。然而, .join() 让我失望了。 sorted() 返回一个列表, .join() 遍历列表中的每个元素以将其附加到字符串中。所以应该是线性运算。

因此,对于嵌套循环,我的子字符串排序器是否会是 O(n^2) * O(nlogn) 用于对每个结果进行排序 * O(n) 用于加入? Ergo O(n^4logn)??

如果是这样,拆分运营是否会提高效率?我有另一个实现,我将子字符串的排序移动到第二个列表理解

substr = [s[i: j] for i in range(len(s)) 
                for j in range(i + 1, len(s) + 1)]

sortedSubstr = ["".join(sorted(s)) for s in substr]

这将使其首先成为 O(n^2) 列表理解 + O(n)*O(nlogn) 用于第二个列表理解

现在制作整个程序 O(n^2logn)

如果我错了,请纠正我。谢谢

  • 你只加入一次,加入的成本是其输入长度的总和。那么你为什么要*乘*乘以 O(n)?连接的成本是所有子字符串的长度之和,加上创建每个要连接的字符串的成本之和。
  • 因为每个 .join() 都针对列表中的每个子字符串发生。它不是只做一次,而是针对理解的每次迭代
  • 这不会改变参数长度的总和。无论是一次性完成还是分成一堆调用,总和都是相同的

【解决方案1】:

对于第一个算法,时间复杂度是 O(n^3*log(n)) ,因为在两次循环之后,您不会为 sorted 中的每个原子动作创建 join 。您分别排序和加入。所以 O(n) + O(n*log(n)) = O(n*log(n)) ,乘以 O(n^2) (嵌套循环)得到 O(n^3*log(n))

关于第二种算法。

  • substr 的计算为我们提供了 O(n^3) :嵌套循环乘以 O(n) 的相同 O(n^2) 切片 s
  • 请注意, len(substr) O(n^2) — 对于嵌套循环中的每个 (i, j)
  • sortedSubstr 的计算得到 O(n^3*log(n)) :对于 substr (其计数为 O(n^2) )的每个元素,我们调用 sorted 。每个元素的 len O(n) ,所以 sorted(s) 给了我们 O(n*log(n)) 。所以,同样, O(n^2) * O(n*log(n)) = O(n^3*log(n))
  • 计算 substr ( O(n^3) ) 加上计算 sortedSubstr ( O(n^3*log(n)) ) 得到 O(n^3*log(n))

所以第二次使用相同的 O(n^3*log(n))