门|门CS 2012 |问题37

一个由n个字符串组成的列表，每个字符串的长度为n，使用合并排序算法按字典顺序排序。这种计算的最坏运行时间是 （A） O（n日志n） （B） O（n） ^2. 日志（n） （C） O（n） ^2. +日志（n） （D） O（n） ^2. ) 答复: （B） 说明：

当我们对n个整数数组进行排序时，涉及的比较总数的递推关系为，

T（n）=2T（n/2）+（n），其中（n）是为了合并大小为n/2的2个排序子阵列而进行的比较次数。 =（nlog2n）

与比较需要O（1）时间的整数不同，我们得到了n个字符串。我们可以比较O（n）最坏情况下的两个字符串。因此，现在的比较总数将是（n2log2n），其中每个比较现在需要O（n）个时间。

一般来说，合并排序会进行（nlog2n）比较，如果每次比较都能在O（1）时间内完成，则会在（nlog2n）时间内运行。

见本报告问题5 https://www.geeksforgeeks.org/data-structures-and-algorithms-set-28/

这个解决方案是由 Pranjul Ahuja 这个问题的小测验