求大神帮忙分析以下代码的效率

C++ 字符串函数 replace find 时间复杂度

代码1：

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string A,B;
	getline(cin,A);
	getline(cin,B);	
	for(int i=0;i<B.length();i++)
	for(int j=0;j<A.length();j++)
	if(A[j]==B[i])
 	{
	 	A.replace(j,1,"");
	 	j--;
	 }
 	cout<<A;
	return 0;
}

代码2：

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string A,B;
	int t,index=0;
	getline(cin,A);
	getline(cin,B);	
	for(int i=0;i<B.length();i++)
	{
		index=0;
		while((t=A.find(B[i],index))!=string::npos)
 		{
		 	A.replace(t,1,"");
		 	index=t;
		 }
	}
 	cout<<A;
	return 0;
}

代码1提交后最后一个测试点直接运行超时，题目时间限制是100ms，超过100ms了，代码1的时间复杂度是多少？replace是不是相当于删除操作，复杂度为O(N)？代码2提交通过，最后一个测试点仅8ms，代码2的时间复杂度是多少？find的时间复杂度是不是O(1)？？
哪位大佬帮忙分析下代码1和代码2的效率，为什么会有这么大差距？

3 个解决方案

#1

代码3：

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string A,B;
	int book[256]={0};
	getline(cin,A);
	getline(cin,B);	
	for(int i=0;i<B.length();i++)
	book[B[i]]=1;
	for(int i=0;i<A.length();i++)
	if(!book[A[i]])
	cout<<A[i];
	return 0;
}

代码3提交后也能过，最后一个测试点5ms，和代码2同级别，代码3很容易看出是O(N)的复杂度，那么代码2也是O(N)的复杂度，那么find和replace操作难道都是O(1)的复杂度？？？求大佬帮忙解释下为什么。

#2

无profiler不要谈效率！

#3

引用 2 楼 zhao4zhong1 的回复:

无profiler不要谈效率！

你说的我听不懂，我的表述可能不严谨，但我只是想让懂C++的人分析下时间复杂度，没有那么复杂，如果你不能回答，请离开。