#include <bits/stdc++.h> using namespace std; string s1,s2; int cnt1,cnt2; string cann(const string &s){ cnt1++; int n=s.size(); if(n%2){ return s; } string a=s.substr(0,n/2); string b=s.substr(n/2,n/2); a=cann(a); b=cann(b); if(b<a){ swap(a,b); } return a+b; } bool g(int l1,int r1,int l2,int r2){ cnt2++; string a=s1.substr(l1,r1-l1+1),b=s2.substr(l2,r2-l2+1); if(a==b){ return 1; }else if((r1-l1+1)%2 || (r2-l2+1)%2){ return 0; } int mid1=(l1+r1)/2,mid2=(l2+r2)/2; if(g(l1,mid1,l2,mid2)&&g(mid1+1,r1,mid2+1,r2)||g(l1,mid1,mid2+1,r2)&&g(mid1+1,r1,l2,mid2)){ return 1; } return 0; } int main(){ for(int i=1;i<=1000000;i++){ for(int j=1;j<=3;j++){ s1=s2=""; srand(time(NULL)); for(int k=1;k<=pow(2,j);k++){ s1+=char(rand()%26+'a'); } for(int k=1;k<=pow(2,j);k++){ s2+=char(rand()%26+'a'); } cnt1=cnt2=0; if(cann(s1)==cann(s2)){ cout << "YES" <<endl; }else{ cout << "NO" << endl; } if(g(0,s1.size()-1,0,s2.size()-1)){ cout << "YES" << endl; }else{ cout << "NO" << endl; } cout << s1 << " " << s2 << endl; cout << setw(5) << cnt1; cout << setw(5) << cnt2; cout << " " << (cnt1<=cnt2) << endl; } } return 0; } 那个函数时间复杂度更低

这段代码中包含两个函数：`cann()`和`g()`。我们来分析一下它们的时间复杂度。

首先是`cann()`函数。这是一个递归函数，它将字符串分成两半，然后递归地调用自身，并将结果合并起来。因为每次递归都会将字符串长度缩小一半，所以递归的深度是O(log n)。在每一层递归中，都需要进行字符串的拼接操作，时间复杂度是O(n)，其中n是字符串的长度。所以总体来说，`cann()`函数的时间复杂度是O(n log n)。

接下来是`g()`函数。这个函数用来比较两个字符串是否相等，但是在比较之前会先检查字符串长度是否为偶数，如果不是偶数则返回false。然后，它将字符串分成两半，然后分别对子字符串进行递归调用，并根据递归结果进行判断。在每一层递归中，都需要进行字符串的比较操作，时间复杂度是O(n)，其中n是字符串的长度。因为每次递归都会将字符串长度缩小一半，所以递归的深度是O(log n)。所以总体来说，`g()`函数的时间复杂度是O(n log n)。

综上所述，`cann()`和`g()`函数的时间复杂度都是O(n log n)，它们的时间复杂度是相同的，没有明显的差异。