|
1、时间复杂度：是衡量算法优劣的一项标准 通常 T=O(n) ，在数学中类似 y=f(x) f(x)=3*x -> y=3*x -> 随着x逐渐增大，y也会逐渐增大，在坐标系上呈现直线 T=O(n) 随着数据量n逐渐变化，时间复杂度T也会逐渐变化，这里的O时间复杂度函数 时间复杂度是指基本代码执行的次数，基本代码通常指循环最里层的代码 输入一个n，输入n个数字，将n个数字变成相反数再输出 for(int i=0;i<n;i++){ cout<<-a[i]<<" ";//基本代码 } T=O(n) 随着n逐渐增大，T也逐渐增大 输入一个n，输入n个数字，将n个数字从小到大排序再输出 for(int i=0;i<n;i++){ for(int j=0;j<n-i;j++){ if(a[j]>a[j+1]) swap(a[j],a[j+1]);//基本代码 } } T=O(n^2) 随着n逐渐增大，T也逐渐增大，增大的幅度逐渐变大 输入一个n，输入n个数字（有序），输入一个m，输出m是否在这n个数中 int l=0,r=n-1; while(l<r){ int mid=(l+r)/2; if(...) ..; else ..; } T=O(logn) 数学的对数函数，c++底数通常忽略，随着n逐渐增大，T也逐渐增大，增大的幅度逐渐变变小 递归求斐波那契数列 int feib(int n){ if(n<2) return 1; return feib(n-1)+fei(n-2); } T=O(2^n) 随着n逐渐增大，T也逐渐增大，增大的幅度逐渐变大 输入一个数字，输出它是奇数还是偶数 T=O(1) 时间复杂度T，与数据量没关系，通常记作常数级，O(1) 时间复杂度是【估算】 平面直角坐标系：略 O(1)>O(logn)>O(n)>O(nlogn)>O(n^2)>O(2^n)>O(n!) O(nlogn) 是快速排序的平均时间复杂度（与基准数字的具体数值有关） --------------------------------------------------- 2、字符串哈希 输入n，输入n个数字，输入m，在这n个数字中，m是否存在 for(int i=0;i<n;i++){ if(a[i]==m)...; } 解法：O(n) 先排序sort O(nlogn),再二分 O(logn),因为O((n+1)logn)与O(nlogn)接近， 所以可以认为这样的解法符合O(nlogn)。 输入n，输入n个字符串，字符串的长度为k，输入字符串m，在这n个字符串中，m是否存在 for(int i=0;i<n;i++){ if(a[i]==m)...; } 因为字符串判断时间复杂度是O(n)，因此该解法为O(nk) 字符串连接，长度n*k，再find，时间复杂度还是O(nk) 若O(nk)超时了，怎么办？ 将字符串看成数字 字符串哈希：将一个字符串转化成一个整数，并且保证每个字符串转化的整数都不同，这个整数就是这个字符串的哈希值 这样可以通过哈希值判断字符串是否出现过，时间复杂度降低到O(n) 如：abc 1 bca 2 ccc 3 mkk 6 将字符串转化成哈希值的函数，也叫哈希函数 哈希冲突率：计算哈希值时，有一定概率使不同字符串的哈希值相同，这个叫做哈希冲突 如： //返回长度 int hash1(string s){ return s.size(); } abc=3 ccc=3 bac=3 哈希冲突率越小，哈希函数越完美 //返回每个字符的ascii之和 int hash2(string s){ int hs=0; for(int i=0;i<s.size();i++){ hs+=s[i]; } return hs; } abc=bac=cba=294 //将计算哈希值的方法逐渐优化，降低哈希冲突率 int hash3(string s){ int hs=0; for(int i=0;i<s.size();i++){ hs=hs*10+s[i]; } return hs; } 修改先后次序的权重，实现abc、bac、cba哈希值不同 int hash4(string s){ int hs=0; for(int i=0;i<s.size();i++){ hs=hs*128+s[i]; } return hs; } //将字符组成的字符串根据ascii码的值看成128进制 int n; cin>>n; string s,m; int a[100000]={}; for(int i=0;i<n;i++){ cin>>s; a[i]=hash4(s); } cin>>m; int b=hash4(m); for(int i=0;i<n;i++){ if(b==a[i]) ..; } //写哈希算法（保证只有小写字母） int getchs(char c){ return c-'a'+1;//降低值 } //进制的选择：通常需要比数据种类大，通常取质数 //26个字母29，128个字符131，256个字符257 int jz=29; int mod=1000000007;//超过范围进行取模 //hash("abc")=hash("ab")*jz+getchs('c') string s="abcdefgh";// vector<long long> hs(s.size()+1,0);//长度，初始值 vector<long long> hss;//多个字符串的哈希值 void hashqz(string s){ //一次遍历计算出所有前缀哈希值，hs[s.size()]代表s的哈希值 for(int i=1;i<=s.size();i++){ hs[i]=(hs[i-1]*jz+getchs(s[i-1]))%mod; //0+1=>0*10+1=1 //1+2=>1*10+2=12 //12+3=>12*10+3=123 } hss.push_back(hs[s.size()]); } void hashhz(string s){ //一次遍历计算出所有后缀哈希值，hs[s.size()]代表s的哈希值 //3=>3 //2+3=>2*10+3 //1+23=>1*100+23 //hs["abc"]=getchs('a')*jz^?+hs["bc"] int jzs=1; for(int i=s.size()-1;i>=0;i--){ hs[s.size()-i]=(getchs(s[i])*jzs+hs[s.size()-i-1])%mod; //hs[0]=0, c->3 hs[1]=3*1+hs[0]= //jzs->29, b->2 hs[2]=2*29+hs[1]= //jzs->29^2, a->1 hs[3]=1*29^2+hs[2]= jzs*=jz; jzs%=mod; } } int main(){ int n; cin>>n; for(int i=0;i<n;i++){ cin>>s; hashqz(s); } } abc 3 23 123 作业： 自己梳理并完成：输入一个字符串，输出所有前缀和后缀哈希值的程序 完成：ybt.ssoier.cn:8088/problem_show.php?pid=1458 (责任编辑：admin) |