合并运行时间字典分类排序最坏的情况？

本文介绍了合并运行时间字典分类排序最坏的情况？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

每个长度为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）