GESP 五级知识点思维导图

这是一篇关于GESP五级思维导图的思维导图，主要内容包括：复杂模拟，基础数据结构，基础算法，初等数论，算法复杂度的估算（含多项式、指数、对数复杂度）。

GESP五级思维导图

• 算法复杂度的估算（含多项式、指数、对数复杂度）
• 初等数论
  • 素数表的埃氏筛法和线性筛法
    • 埃氏筛法
    • 线性筛选
  • 辗转相除法（也称欧几里得算法）
    • 求某数所有因数—试除
  • 唯一分解定理
    • 判断质数
      • 试除法---算法复杂度：O(n）
        • 数学概念
          • d 能被n整除，则 n/d 也能被n整除 例如： n =12 d = 3 , n/d = 4, 4 也能被12整除 d =2, n/d = 6，2 也能被12整除 d 和n/d是成对出现的，因此可以枚举每队中的较少值来减少枚举数 d<= n/d 推导出 ----> d*d <=n
          • 因此有3种循环： i*i <= n i <= sqrt(n) i <= n/i
        • bool is_prime(int n){ if(n<2) return false; for(int i=2;i<=n/i;i++) { if(n%i==0) return false; } return true; }
        • bool is_prime(int n){ if(n<2) return false; for(int i=2;i*i<n;i++) { if(n%i==0) return false; } return true; }
        • bool is_prime(int n){ if(n<2) return false; int p =sqrt(n); for(int i=2;i<=p;i++) { if(n%i==0) return false; } return true; }
    • 分解质因式
      • 算法复杂度： O(logn~n)
      • 数学知识：n中最多只包含一个大于根号n的质因子（优化)*
      • 质因数分解是将一个合数分解为若干个质数相乘的形式。 例如，数字12可以分解为2×2×3，其中2和3都是质数
      • struct ps { long long num; int cnt; }; vector<ps> vPrimes; void divide(int n){ for(int i=2;i<=n/i;i++){ if(n%i==0) { int s=0; while(n%i==0){ -----这里去合数，例如： 2*2*2*2，直到不能被2除为止 n/=i; s++; } cout<<i<<' '<<s<<endl; struct ps tmp; tmp.num =i; tmp.cnt = s; vPrimes.push_back(tmp); } } if(n>1) cout<<n<<' '<<1<<endl; }
  • A和B的最小公倍数就为A和B的乘积再除以它俩的最大公约数
    • int lcm( int x , int y ) { return （x*y) / gcd(x,y); }
  • 完全平方数
    • 完全平方数的定义，完全平方数开根号以后是一个整数，而非完全平方数开根号之后不是一个整数. n开平方之后用int将其取整，再用取整后的值进行平方操作， 如果和原来相同，说明这是一个完全平方数， 反之则说明这不是一个完全平方数
      • bool ispfs(int n) { int tmp = sqrt(n); if(tmp*tmp ==n) { return true; } else { return false; } }
• 基础算法
  • 二分查找/二分答案（也称二分枚举法）
    • 二分查找
  • 分治算法（归并排序和快速排序）
    • 快速排序
    • 归并排序
  • 贪心算法
    • 什么是贪心
      • 贪心的本质是选择每一阶段的局部最优，从而达到全局最优。 这么说有点抽象，来举一个例子： 例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？ 指定每次拿最大的，最终结果就是拿走最大数额的钱。 每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。
    • 安心解题套路
      • 贪心算法一般分为如下四步： 将问题分解为若干个子问题 找出适合的贪心策略 求解每一个子问题的最优解 将局部最优解堆叠成全局最优解
• 基础数据结构
  • 递归
    • 递归三部曲
      • 确定边界
      • 确定递归函数
      • 确定剪枝条件
  • 单链表、双链表、循环链表
    • 单链表
    • 双链表
    • 循环链表
    • 链表和数组区别
• 复杂模拟
  • （C++）数组模拟高精度加法、减法、乘法、除法
    • 加法
    • 减法
    • 乘法
    • 除法