参考文献

  • 算法第四版

算法分析中常见函数

描述 记号 定义
调和级数 HNH_{N} 1+1/2+1/3+1/4+...+1/N1+1/2+1/3+1/4+...+1/N
阶乘 N!N! 1∗2∗3∗4∗...∗N1*2*3*4*...*N

算法分析中常用的近似函数

描述 近似函数
调和级数求和 HN=1+1/2+1/3+1/4+...+1/N∼lnNH_{N}=1+1/2+1/3+1/4+...+1/N \sim lnN
等差数列求和 1+2+3+4+...+N∼N2/21+2+3+4+...+N \sim N^{2}/2
等比数列求和 1+2+4+8+...+N=2N−1∼2N1+2+4+8+...+N=2N-1 \sim 2N,其中N=2nN=2^{n}
斯特灵公式 lg⁡N!=lg⁡1+lg⁡2+lg⁡3+...+lg⁡N∼Nlg⁡N\lg{N!}=\lg1+\lg2+\lg3+...+\lg_{}{N} \sim N\lg{N}
二项式系数 {Nk}∼Nk/k!\begin{Bmatrix} N\\k\end{Bmatrix} \sim N^{k}/k! ,其中k为小常数
指数函数 (1−1/x)x∼1/e(1-1/x)^x \sim 1/e

典型的静态方法的实现

计算一个整数的绝对值

1
2
3
4
5
6
7
public static int abs(int x){
    if(x  <  0){
      return -x;
    }else{
      return x;
    }
}

计算一个浮点数的绝对值

1
2
3
4
5
6
7
public static double abs(double x){
     if(x < 0.0){
       return -x;
     }else{
       return x;
     }
}
判定一个数是否是素数
1
2
3
4
5
6
7
8
9
10
11
public static boolean isPrime(int N){
      if(N < 2){
        return false;
      }
      for(int i = 2; i*i <= N; i++){
        if(N % i == 0){
          return fasle;
        }
      }
      return true;
}

计算平方根(牛顿迭代法)

1
2
3
4
5
6
7
8
9
10
11
public static double sqrt(double c){
		if(c < 0){
			return Double.NaN;
		}
		double err = 1e-15;
		double t = c;
		while(Math.abs( t- c/t) > err * t){
			t = (c / t + t) / 2.0;
		} 
		return t;
}

计算直角三角形的斜边

1
2
3
public static double hypotenuse(double a,double b){
  return Math.sqrt(a*a + b*b)
}

计算调和级数

1
2
3
4
5
6
7
public static double H(int N){
    double sum = 0.0;
    for(int i = 1; i <= N; i++){
      sum += 1.0 / i;
    }
    return sum;
}

小技巧

取模运算的特殊情况

  • 如果arr.length是2的幂次方,你可以使用位与操作 (&) 来代替模运算 (%).具体来说,如果 arr.length是 2n2^n,那么 round % arr.length等价于 round & (arr.length - 1)

除法与乘法的替代

  • 除以2的幂次方: x // 2^n可以用x >> n替代
  • 乘以2的幂次方: x * 2^n可以用x << n替代

快速判断奇偶性

  • 判断一个数是否为奇数: x % 2 != 0 可以用 x & 1 != 0 替代
  • 判断一个数是否为偶数: x % 2 == 0 可以用 x & 1 == 0替代

快速清零低位

  • 清零最低的n位:x & ~((1 << n) - 1) 例如,清零最低的3位: x & ~7

判断是否为2的次幂

  • (val & -val) == val利用了补码的特性判断一个整数是否为2的次幂