use*_*879 2 algorithm complexity-theory asymptotic-complexity
使用合并排序算法将每个长度为n的n个字符串的列表排序为字典顺序.最坏的情况是这个计算的运行时间是？
我把这个问题作为功课.我知道在O(nlogn)时间内合并排序排序.对于长度的词典顺序是n次nlogn？还是n ^ 2？
算法的每个比较是O(n)[比较两个字符串是O(n)最坏的情况 - 你可能会检测到哪个只在最后一个字符上"更大"],你O(nlogn)在mergesort中进行了比较.
因此,你得到 O(nlogn * n) = O(n^2 * logn)