字符串排序时间复杂度分析

有人问我了一个时间复杂度分析的问题,作为学长,必须答对。
结果不出所料,答错了。觉得这是个值得写下来注意的问题,于是乎……

问题是这样的:

输入是一个字符串数组,要求对数组里面的每个字符串排序,然后再对整个数组排序,问时间复杂度。

设:
数组的长度:N
数组中最长字符串的长度:M

字符串排序

字符串的排序复杂度:M logM
数组里面有N个字符串,总共花费的时间:N M logM

数组排序

整个数组有N个字符串
当两个字符串进行对比时,时间复杂度并不为O(1),而是O(M)
而用快速排序,需要比较 N log N 次,所以数组排序会花费:M N log N

最终,时间复杂度

O(M N (log M + log N))

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容