#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; } 那个函数时间复杂度更低
时间: 2024-04-09 18:29:56 浏览: 11
这段代码中包含两个函数:`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),它们的时间复杂度是相同的,没有明显的差异。
相关问题
#include <bits/stdc++.h> using namespace std
这段代码是一个C++的头文件引用和命名空间的使用示例。具体来说,`#include <bits/stdc++.h>`是一个常用的头文件引用方式,它包含了C++标准库中的所有头文件。而`using namespace std`则是为了使用`std`命名空间中的标准库函数和对象,这样就可以直接使用`cout`、`cin`等标准输入输出流对象,而不需要写`std::cout`、`std::cin`。
这种写法虽然方便,但也存在一些问题。首先,包含了所有的标准库头文件可能会导致编译时间变长。其次,使用了`using namespace std`会将整个`std`命名空间中的所有标识符引入当前作用域,可能会导致命名冲突。因此,在实际开发中,建议根据需要只包含需要的头文件,并使用具体的命名空间来避免潜在的问题。
#include <bits/stdc++.h> using namespace std;
这个头文件是C++11标准引入的,它包含了所有标准库中的头文件。使用这个头文件可以方便地在一个地方包含所有需要的头文件,而不需要一个一个地包含。这个头文件通常只在竞赛中使用,因为它不是标准C++头文件,不保证在所有编译器中都能正常工作。
以下是一个使用这个头文件的示例,实现输入4个整数a、b、c、d,将它们倒序输出:
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << d << ' ' << c << ' ' << b << ' ' << a << endl;
return 0;
}
```