2023年7月30日发(作者：)

算法时间复杂度分析专题⼀（帮助快速解题）笔试：题⽬告诉数据范围，根据题⽬的数据范围来考虑⽤什么解法c++竞赛：⼀般时限1~2秒时间范围内指令操作次数<10^8不同数据范围下，代码时间复杂度和算法该如何选择：1. n<=30,指数级别，=> dfs+剪枝,状态压缩dp2. n=100，考虑时间复杂度O（n^3），=> floyd，dp3. n=1000,考虑时间复杂度O（n^2）或O (n^2longn),=> 枚举或者dp4. n=10000,考虑时间复杂度O（n*sqrt(n)），=> 质数，块状链表5. n=100000,考虑时间复杂度O(nlogn)，=> 各种排序sort，树状数组，set/map平⽅数，heap堆、图论digkstra+heap、spfa、⼆分，求凸包，半平⾯交6. n=1000000,考虑时间复杂度O(n)及常熟较⼩的O（nlogn）=> hash表，双指针扫描，Kmp、AC⾃动机；O（nlogn）的做法：=> sort、树状数组、heap、dijktra、spfa7. n=10000000,考虑时间复杂度O(n)，=> 双指针扫描、Kmp、AC⾃动机、线性筛素数8. n=10^9,考虑时间复杂度O（sqrt(n)）=> 判断质数9. n=10^18,考虑时间复杂度O(logn),=> 最⼤公约数假设n=100000，对应的O(n)=100000;O(n^2) =10^10;O(nlogn)=20n=2*10^51.欧⼏⾥得算法：求两个正整数的最⼤公约数，时间复杂度O（logn）代码:int gcd(int a,int b){

return b?gcd(b,a%b):a; }

2.扩展欧⼏⾥得算法裴蜀定理：若a,b是整数，且（a，b）=d，那么对于任意的整数x，y，ax+by都⼀定是d的倍数，特别地，⼀定存在整数x，y，使得ax+by=d成⽴。代码:int exgcd(int a,int b,int &x,int &y){ if(!b){ x=1;y=0; return a; } int d=exgcd(b,a%b,y,x); y-=(a/b)*x; return d; }

3.线性筛素数：可以在O（n）的时间复杂度内求出1~n之间的所有质数int primes[N],cnt;bool st[N];void get_primes(int n){ for(int i=2;i<=n;i++){ if(!st[i]) primes[cnt++]=i; for(int j=0;j

} } }

4.链表：线性扫描O(n)题⽬：给定⼀个有序链表，请删除其中的重复元素，使得原链表的元素仅出现⼀次。样例1：输⼊：1->1->2输出：1->2样例2：输⼊：1->1->2->3->3输出：1->2->3算法:线性扫描O(n)从前往后扫描整个链表，如果⼀个节点和其后继节点相同，则直接删除后继节点，否则指针移动到后继节点。时间复杂度分析：整个链表只扫描⼀遍，所以为O（n）代码：/*Definition for singly-linked liststruct ListNode{ int val; ListNode *next; ListNode(int x);val(x),next(NULL){}};

*/class Solution{public : ListNode* deleteDuplicates(ListNode* head){ if(!head) return head; ListNode* p=head; while(p->next) { if(p->val==p->next->val) p->next=p->next->next; else p=p->next; } return head; }};5.归并排序题⽬：给出两个排好序的单向链表，返回合并排序后新的单向链表。链表结点的数据结构：struct ListNode{ int val; ListNode *next; ListNode(int x);val(x),next(NULL){} }};

样例：输⼊:1->2->4,1->3->4返回：1->1->2->3->4->4算法：线性合并O（n）1.新建头部的保护结点dummy，设置cur指针指向dummy。2.若当前l1指针指向的结点值val⽐l2指针指向的结点的值val⼩，则令cur的next指针指向l2，且l2后移。3.然后cur指针按照上⼀部分设置后的位置后移。4.循环以上步骤直到l1或l2为空。5.将剩余的l1或l2接到cur指针后⾯。时间复杂度：两表各遍历⼀遍，所以为O（n）代码：/*Definition for singly-linked liststruct ListNode{ int val; ListNode *next; ListNode(int x);val(x),next(NULL){} }};

*/class Solution{public : ListNode* mergeTwoLists(ListNode* l1,ListNode* l2){ ListNode*dummy=new ListNode(0); //⼀开始分别指向两个头结点 ListNode *cur=dummy; while(l1！=NULL&&l2!=NULL){ if(l1->valval){ cur->next=l1; l1=l1->next; } else{ cur->next=12; l2=l2->next; } cur=cur->next; } cur->next=(l1!=NULL?l1:l2); return dummy->next; }

};6.深度优先搜索DFS题⽬：给定⼀个字符串，返回由该数字⼦串所能代表的所有字母的组合。每个数字能代表⼀些字母，和九宫格键盘⼀样。样例：给定⼦串“23”，返回所有字母组合[“ad”、“ae”、“af”、“bd”、“be”、“bf、”cd"、“ce”、“cf”]。算法：深度优先搜索DFS：O（4^l）1.可以通过⼿⼯或者循环的⽅式预处理每个数字可以代表哪些字母。2.使⽤深度优先搜索DFS，每层递归尝试拼接⼀个新字母。3.递归到头，将当前字母串加⼊到答案中。注意：有可能数字串是空串，需要特盘。时间复杂度：使⽤了递归⽅式，时间复杂度与答案个数相同，设数字串长度为l，则最坏时间复杂的为O（4^l）循环数据，根据每⼀位选字母，依次枚举2：代表a，b，c3：代表d，e，f对应的每个字母枚举⼀遍，总⽅案数就是每个字母所能代表的字母数的乘积代码：class Solution{public : vector digit[10]; vector res;

void init(){ char cur='a'; for(int i=2;i<10;i++){ for(int j=0;j<3;j++) digit[i].push_back(cur++); if(i==7||i==9) digit[i].push_back(cur++); } }

void dfs(string digits,int d,string cur){ if(d==()){ _back(cur); return; }

int cur_num=digits[d]-'0';

for(int i=0;i

vector letterCombinations(string digits){ if(digits=="") return res; init(); dfs(digits,0,""); return res; }};