算法-前置知识
参考文献
- 算法第四版
算法分析中常见函数
描述 | 记号 | 定义 |
---|---|---|
调和级数 | ||
阶乘 |
算法分析中常用的近似函数
描述 | 近似函数 |
---|---|
调和级数求和 | |
等差数列求和 | |
等比数列求和 | ,其中 |
斯特灵公式 | |
二项式系数 | ,其中k为小常数 |
指数函数 |
典型的静态方法的实现
计算一个整数的绝对值
1 | public static int abs(int x){ |
计算一个浮点数的绝对值
1 | public static double abs(double x){ |
判定一个数是否是素数
1 | public static boolean isPrime(int N){ |
计算平方根(牛顿迭代法)
1 | public static double sqrt(double c){ |
计算直角三角形的斜边
1 | public static double hypotenuse(double a,double b){ |
计算调和级数
1 | public static double H(int N){ |
小技巧
取模运算的特殊情况
- 如果
arr.length
是2的幂次方,你可以使用位与操作 (&
) 来代替模运算 (%
).具体来说,如果arr.length
是 ,那么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的次幂
https://www.holelin.cn/2022/01/18/algorithm/%E7%AE%97%E6%B3%95-%E5%89%8D%E7%BD%AE%E7%9F%A5%E8%AF%86/
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 HoleLin's Blog!