algorithm - 用于单词列表排列的大 O 表示法

Question

长度为 n 的单词列表的字符排列列表的长度的大 O 表示法是什么？

我只是不知道如何表达，因为它会像 n!对于每个单词，其中 n 是该单词的字符，但 O(n!) 只是单个单词的复杂度，而不是 n 个单词的列表。

此外，每个单词可能有不同的大小。

一个例子:

假设我有单词“abc”、“abcd”和“abcde”。如果我必须创建每个单词的排列，我最终会得到一个长度为 6、24 和 120 的字符串列表列表，即“abc”的排列将在第一个列表中，第二个单词的排列将在第二个等等。

如果我使用置换迭代器，生成所有这些列表需要多少时间？

Answer 1

因为 BigO 代表一个上限，那么你可以安全地说有 O(k*n!) 个字符串，其中 n 是最长输入单词的长度(因为在最坏的情况下所有字符串将具有相同的长度那么将恰好有 k*n! 个排列，在更好的情况下，可变长度的数字将是 < k*n!，但符号 O(k*n!) 仍然有效)。

如果您有一些关于这些长度分布的额外信息，我们可以尝试进行更严格的限制:-)

@Edit:正如@Aron 指出的那样，如果您没有重复字符，这是一个非常严格的上限(我不会在这里变得非常正式)。对于重复字符，它仍然是一个有效的上限，但更严格的限制是 O(k*a^n)，其中 a 是我们字母表的大小(如果您使用英语，则为 26，如果您使用 Unicode，则超过 110,000)这最终将比 O(k*n!) 更严格。这是因为在一个单词的每个 n 槽中，您可以放置​​ a 个字符之一，并注意重复字符 a 可能比 n 更小(甚至小得多)。