C++ 中带有自定义比较器函数的 sort() 的时间和空间复杂度是多少？

Question

考虑以下代码 -

 bool cmp(pair<string,int> &a, pair<string,int> &b) {
     return ((a.second > b.second) || (a.second==b.second && a.first<b.first));
 }

vector<pair<string,int>> v;

sort(v.begin(),v.end(),cmp);

对于这种情况，我的复杂性是多少？那将会O(nlogn)？

Answer 1

std::sort时间复杂度：O(NlogN) 自定义比较。
但在你的情况下，比较器函数cmp还执行字符串比较，

(a.第二==b.第二 && a.第一<b.第一)

std::basic_string operator< 时间复杂度与字符串的大小成线性关系。

因此，最坏情况的复杂度是O(K*NlogN) 字符比较，其中 K 是字符串的长度。