一个时间复杂度的问题
有一个字符串数组, 将数组中的每一个字符串按照字母序排序,之后再将整个字符串数组按照字典序排序。整个操作的时间复杂度?
解:
假设最长的字符串长度为s; 数组中有n个字符串
对每个字符串排序: O(slogs)
将数组中的每一个字符串按照字母序排序: O(n*slog(s))
再将数组按照字典来排序: O(s*nlog(n))
合并起来就是O（n*slog(s)）+O（s*nlog(n)）= O（n*s*logs + s*n*logn）
解析: 开始我不理解的是为何是log 为何不是其他 参考下面这个图
一般考虑他为平均情况就行了
1.我们使用快速排序算法平均情况就为nlogn
2.对数组中最长的字符字符进行排序的话则为O(slogs)
3.再将他们按照字母序来排则为 O(n*slogs)
4.再用字典序来排序则为O(s*nlog(n))
5.合并起来就是O（n*slog(s)）+O（s*nlog(n)）= O（n*s*logs + s*n*logn）