algorithm - 为文件中的每一行生成一行中所有单词对的复杂性

Question

所以我有一个包含文本行的文本文件。我正在逐行读取文件，对于每一行，我生成每个单词的所有可能的 2 对，其中顺序无关紧要。例如，给定行 'How are you' 我生成的是 ['how are' ,'how you' , 'are you']。我的问题是这样做的时间复杂度是多少？我知道读取文件中的每个单词需要 O(n) 并且需要 O(n^2) 来生成对，所以 O(n^3) 因为对于每一行我都在做 O(n^2) 的工作量？

Answer 1

假设您有 n行和最大长度(字数)是k .那么你的复杂度就是 O(n*k^2) .区分行数和行的长度很重要，因为一般情况下，文件往往有很多行，而行的长度通常很小。

但是，假设您很少排长队。如果你的平均长度是 k'那么你可能会认为你的摊销运行时间是O(n*k'^2) .但是请考虑第一行的长度为 n*k' 的情况。其余的长度为 0 .那么你的摊销运行时间是O(n^2*k'^2) - 不是你所期望的。你确实可以证明 O(n^2*k'^2)是分摊运行时间的界限。请注意，在上述退化情况下 O(n^2*k'^2)比 O(n*k^2) 更好自 n*k^2等于n*(n*k')^2 = n^3k'^2 .所以只要n^2*k'^2 <= n*k^2 , 即 k'<= k/sqrt(n) (意味着平均长度小于最大长度除以 sqrt(n))然后边界 O(n^2*k'^2)比边界好 O(n*k^2) .