有人问我了一个时间复杂度分析的问题,作为学长,必须答对。
结果不出所料,答错了。觉得这是个值得写下来注意的问题,于是乎……
问题是这样的:
输入是一个字符串数组,要求对数组里面的每个字符串排序,然后再对整个数组排序,问时间复杂度。
设:
数组的长度: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))