算法分析.md

1. 当T(n)=O(f(n))时表明，函数T(n)的增长速度不快于函数f(n)，即f(n)为T(n)的上界

2. 当T(n)=omega(f(n))时表明，函数函数T(n)的增长速度不低于函数f(n)，即f(n)为T(n)的下界

3. 当T(n)=Θ(f(n))时表明，函数函数T(n)的增长速度与函数f(n)相同

4. 欧几里得算法

   public static long gcd(long m,long n){
       while(n!=0){
           long rem = m % n;
           m = n;
           n = rem;
       }
       return m;
   }
   //用于求解两数的最大公因数

5. 幂运算

   // 版本一
   public static long pow(long x,int n){
       if(n==0){
           return 0;
       }
       if(n==1){
           return x;
       }
       if (n % 2 == 0) {
           return pow(x, n / 2)*pow(x, n / 2) ;
       } else {
           return x * pow(x, n / 2)*pow(x, n / 2) ;
       }
   }
   
   //版本二
   public static long pow(long x,int n){
       if(n==0){
           return 0;
       }
       if (n % 2 == 0) {
           return pow(x*x, n / 2) ;
       } else {
           return x * pow(x*x, n / 2) ;
       }
   }
   //相较于版本一减少了递归次数，并且当n=1时是符合else中的条件判定的，可以忽略，当然写上也没什么问题