算法概论
序言
Fibonacci 数列
多项式时间算法：
var fib_arr = [0, 1];
function fib(n){
if(n == 0){
return 0;
}else if(n == 1){
return 1;
}
for (var i = 0; i < n-2; i++) {
fib_arr[n+2] = fib_arr[n+1] + fib_arr[n]
}
return fib_arr[n]
}
var start = new Date().getTime();
console.log(fib(30));
var end = new Date().getTime();
console.log('运行时间：'+(end-start));
// 运行时间：24
指数时间算法：
function fib(n){
if(n == 0){
return 0;
}else if(n == 1){
return 1;
}else{
return fib(n-1) + fib(n-2);
}
}
var start = new Date().getTime();
console.log(fib(30));
var end = new Date().getTime();
console.log('运行时间：'+(end-start));
// 运行时间：50
渐进
- 上界：Ο
- 下界：Ω
- 紧确界：Θ
数字的算法
基础算数
基数和对数
- b 为基数的 k 位数字最大为 b^k-1
- b 为基数表示 N 需要 ⌈log(b)(N+1)⌉ 位（应该是向上取整）
乘法（Al Khwarizmi 乘法规则）
// 类似使用二进制进行乘法（当y>=0时可用）
function multiply(x, y){
if(0 == y){
return 0;
}
var z = multiply(x, Math.floor(y/2))
// z为偶数，z为奇数加到x上
return y%2 == 0 ? 2*z : x + 2*z;
}
console.log(multiply(11, 13));
除法
// 类似使用二进制进行除法（当y>=1时可用，q：quotient，r：remainder）
function divide(x, y){
if(0 == x){
return [0, 0];
}
var z = divide(Math.floor(x/2), y);
var q = 2 * z[0];
var r = 2 * z[1];
if (x%2 == 1) {
// 被除数为奇数除二余数为1
r++;
}
if (r >= y) {
// 余数大于除数，余数变为余数减去除数，商+1
r -= y;
q++;
}
return [q, r];
}
console.log(divide(11, 13));
模运算
-
x 模 N=y：N 可以整除 (x-y)，且 0<=y<N
// 求模的指数运算（y>=1）
function modexp(x, y, N){
if(0 == y){
return 1;
}
var z = modexp(x, Math.floor(y/2), N);
if (y%2 == 0) {
return (z * z) % N;
}else{
return (x * z * z) % N;
}
}
console.log(modexp(11, 11, 2));//1
console.log(modexp(10, 11, 2));//0
console.log(modexp(10, 3, 13));//12// 求模的除法运算
// 太难，先留着
最大公因数算法
-
Euclid 规则：如果 x，y 是正整数，且有 X>=y，那么 gcd(x, y) = gcd(x mod y, y)
// Euclid求最大公约数方法（a>=b>=0）
function euclid(a, b){
if(0 == b) return a;
return euclid(b, a % b);
}
console.log(euclid(11, 11));//11
console.log(euclid(33, 22));//11
console.log(euclid(97, 79));//1
素性测试
-
费马小定理：p 为素数，任意对于任意 1<=a<p 有
a^(p-1) 模 p=1// 素数测试算法（对于合数N，a的大多数无法通过测试）
function primality(N){
var a = Math.floor(2 + Math.random() * (N-3));
if (modexp(a, N - 1, N) == 1) {
return true;
}else{
return false;
}
}// 求模的指数运算（y>=1），前面的算法
function modexp(x, y, N){
if(0 == y){
return 1;
}
var z = modexp(x, Math.floor(y/2), N);
if (y%2 == 0) {
return (z * z) % N;
}else{
return (x * z * z) % N;
}
}
console.log(primality(11027));
console.log(primality(11026));// 素数测试算法（对于合数N，a的大多数无法通过测试）
function primality(N){
// 降低出错概率到(2^-100)
for (var i = 0; i < 100; i++) {
var a = Math.floor(2 + Math.random() * (N-3));
if (modexp(a, N - 1, N) != 1) {
return false;
}
}
return true;
}// 求模的指数运算（y>=1），前面的算法
function modexp(x, y, N){
if(0 == y){
return 1;
}
var z = modexp(x, Math.floor(y/2), N);
if (y%2 == 0) {
return (z * z) % N;
}else{
return (x * z * z) % N;
}
}
console.log(primality(11027));
console.log(primality(11026));
密码学
一次一密乱码本（one-time pad）和 AES
使用密钥 r 进行异或加密解密
- 加密：er(x) = x ⊕ r
- 解密：er(er(x)) =(x ⊕ r) ⊕ r = x ⊕ (r ⊕ r) = x
一次一密乱码本
r 与发送信息长度一样
const r = "101011100";
function encrypt(x){
return (parseInt(x, 2) ^ parseInt(r, 2)).toString(2);
}
function unencrypt(x){
return (parseInt(x, 2) ^ parseInt(r, 2)).toString(2);
}
// test
var msg = "111110000";
var encrypted = encrypt(msg);
console.log(`encrypted: ${encrypted}`);
var unencrypted = unencrypt(encrypted);
console.log(`unencrypted: ${unencrypted}`);
AES
- r 通常定为 128 位（也有定为 192 位或 256 位的情况）
- 定义一种双向映射机制 er
- 信息分成片段，每个片段用 er 加密
RAS
生成密钥：
- 找大整数 p,q（素数测试算法）
- 根据 N=pq，求 N（乘法）
- 找任意与 (p-1)(q-1) 互素的数 e（Euclid 算法）
- 根据 ed≡(1 mod (p-1)(q-1))，求 d（拓展 Euclid 算法）
此时公钥为 (N,e)，私钥为 (N,d)
加密解密
- 加密：y=x^e mod N
- 解密：x=y^d mod N
算法导论
出现的代码并非完美版，仅供参考！！！
基础
分治模式
三个步骤
- 分解
- 解决
- 合并
渐进
- 上界
- 下界
- 紧确界
- 非渐进紧确上界
- 非渐进紧确下界
性质：传递性、自反性、对称性、转置对称性
最大子数组问题
暴力组合
C(n,2)：效率为 O(n^2)
var arr = [-10,-10,-9,-7,-6,3,20,-9,-8,-7];
// 找出全部可能的结果对比
var max_h = 0, max_r = 0 , max_s = arr[0];
// i从0到n-1
for (var i = 0; i < arr.length - 1; i++) {
var sum = 0;
// j从i到n
for (var j = i; j < arr.length; j++) {
sum += arr[j]
// 判断i-j这个区间是否为“最大”
if (sum > max_s) {
max_h = i;
max_r = j;
max_s = sum;
}
}
}
console.log(max_h, max_r, max_s);
分治
-
分成左右两个数组
-
左边计算最大子数组（递归）
-
右边计算最大子数组（递归）
-
中间计算最大子数组
-
比较左中右返回最大子数组
var arr = [-10,-10,-9,-7,-6,3,20,-9,-8,-7];
// 分治
function find_maximum_subarray(arr, low, high){
if (low == high) {
return {low:low, high:high, max_sum:arr[low]}
}else{
// 递归检查并比较
var mid = Math.floor((low + high)/2);
var left = find_maximum_subarray(arr, low, mid);
var right = find_maximum_subarray(arr, mid + 1, high);
var cross = find_max_crossing_subarray(arr, low, mid ,high);
if(left.max_sum > right.max_sum && left.max_sum > cross.max_sum){
return left;
}else if(right.max_sum > left.max_sum && right.max_sum > cross.max_sum){
return right;
}else{
return cross;
}
}
}// 找穿过mid的最大子数组
function find_max_crossing_subarray(arr, low, mid ,high){
var sum = 0,
// 注意不是MIN_VALUE，MIN_VALUE 属性是 JavaScript 中可表示的最小的数（接近 0 ，但不是负数）。它的近似值为 5 x 10-324。
left_sum = right_sum = Number.NEGATIVE_INFINITY,
max_left,
max_right;
for (var i = mid; i >= low; i--) {
sum += arr[i]
if (sum > left_sum) {
left_sum = sum;
max_left = i
}
}sum = 0;
for (var j = mid+1; j <= high; j++) {
sum += arr[j]
if (sum > right_sum) {
right_sum = sum;
max_right = j
}
}return {
low:max_left, high:max_right, max_sum:left_sum + right_sum
}
}
console.log(find_maximum_subarray(arr, 0, arr.length-1));
非递归
-
0-i 的最大子数组
-
0-i+1 的最大子数组（在已知 0-i 的最大子数组的条件下可在线性时间得出）
=_=
堆排序
快速排序
数据结构
高级设计与分析技术
动态规划
与分治类似，通过组合子问题求解原问题，但动态规划应用于子问题重叠的情况（这种情况用分治会反复求解公共子问题）。
步骤：
- 刻画最优解的结构特征
- 递归定义最优解的值
- 计算最优解的值，采用自底向上的方法
- 利用计算出的信息构造最优解
钢条问题
=_=
矩阵链乘法
=_=