在图像中,我不明白在对字符串数组进行排序时额外的 O(s) 从何而来。我知道对字符串数组进行排序将是 O(a log a),我不明白为什么我们还必须添加 O(s)。
在我看来,O(a log a) 负责对字符串数组中的所有字符串进行排序。
最佳答案
卡在同一个例子上了!请记住,对 n 个字符的数组进行排序需要花费 nlogn
时间。对于最后的排序,如果我们假设数组中的每个字符串的长度为 1,那么我们再次只是对 a
字符进行排序,所以我们得到 aloga
项,但是最差的每个字符串的 case 长度是 s
所以你需要做 aloga
比较 s
次。
关于algorithm - 如何在字符串数组中对字符串进行排序,然后对该数组进行排序,结果是 O(a*s(loga+logs))?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40698602/