合并运行时间字典分类排序最坏的情况？ [英] Merge sort worst case running time for lexicographic sorting?

问题描述

每个长度为n的n个字符串列表分类到使用合并排序算法字典顺序。这个计算的最坏情况下的运行时间是？

A list of n strings each of length n is sorted into lexicographic order using the merge sort algorithm. The worst case running time of this computation is?

我得到这个问题的一门功课。我知道在O（nlogn）时间合并排序排序。对于字典顺序长度是n次nlogn？或N ^ 2？

I got this question as a homework. I know merge sort sorts in O(nlogn) time. For lexicographic order for length in is it n times nlogn ? or n^2 ?

推荐答案

算法的每比较 O（N） [比较两个字符串的 O（N）最坏的情况 - 你可能会发现这是只在最后一个字符大]，你有 O（nlogn）比较在合并排序。

Each comparison of the algorithm is O(n) [comparing two strings is O(n) worst case - you might detect which is "bigger" only on the last character], You have O(nlogn) comparisons in mergesort.

这样你可以获得 O（nlogn * N）=为O（n ^ 2 * LOGN）

这篇关于合并运行时间字典分类排序最坏的情况？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！