为什么不在 GFG 的 Alien Dictionary 问题中进行 n^2 个比较？[关闭]

问：

这是问题陈述（如 GeeksForGeeks 网站上给出的那样）：

给定一个具有 N 个单词和 k 个标准词典起始字母表的外星语言的排序词典，找到外来语言中字符的顺序。

解释：我们得到了一个有 N 个单词的排序词典。这里的字典是一个有序列表。单词是允许的字符序列。允许使用“K”字符。这些字符是罗马文字的第一个 K 字母。例如，K=5 表示允许的字符为 {a， b， c， d， e}。但是，在外星语言中，允许的字符的顺序与标准罗马文字不同。例如，在外来语言中，字符的顺序可以是 [b， d， e， a， c]。给定词典中的单词按词典顺序排序。使用字典，我们必须弄清楚外星语言中字符的顺序。

示例测试用例： N = 5， K = 4， dict = [“baa”，“abcd”，“abca”，“cab”，“cad”]

解：{b， d， a， c}

现在，该解决方案需要生成 DAG。我们遍历字典并将每个单词与下一个单词进行比较，以获取有关外星字典中字母顺序的信息，即成对比较。在最佳方法中，需要 （N-1） 比较才能创建 DAG（N 是字典中的单词数）。每次我们比较 2 个单词时，我们都可以推断出一些关于字母顺序的信息。此信息用于在外星词典中建立字母顺序。

我的第一个直觉是，字典中的每个字符串都可以与它后面的每个字符串进行比较，从而按 N^2 的顺序进行总计比较，即 [（n-1）+（n-2）+...+2+1] 比较。但事实证明，N^2 比较是不需要的。如果我们只使用上一段中提到的 （N-1） 比较，则该信息足以推断出字母顺序。我怎样才能证明在 N^2 方法中进行的额外比较总是多余的，不会提供任何有用的信息？