具有自定义比较器功能的 C++ 中 sort() 的时间和 space 复杂度是多少？

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.second==b.second && a.first<b.first)

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

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