06CS/算法

算法概论

序言

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

  1. r 通常定为 128 位(也有定为 192 位或 256 位的情况)
  2. 定义一种双向映射机制 er
  3. 信息分成片段,每个片段用 er 加密

RAS

生成密钥:

  1. 找大整数 p,q(素数测试算法)
  2. 根据 N=pq,求 N(乘法)
  3. 找任意与 (p-1)(q-1) 互素的数 e(Euclid 算法)
  4. 根据 ed≡(1 mod (p-1)(q-1)),求 d(拓展 Euclid 算法)

此时公钥为 (N,e),私钥为 (N,d)

加密解密

  1. 加密:y=x^e mod N
  2. 解密: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);

分治

  1. 分成左右两个数组
  2. 左边计算最大子数组(递归)
  3. 右边计算最大子数组(递归)
  4. 中间计算最大子数组
  5. 比较左中右返回最大子数组
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));

非递归

  1. 0-i 的最大子数组
  2. 0-i+1 的最大子数组(在已知 0-i 的最大子数组的条件下可在线性时间得出)
=_=

堆排序

快速排序

数据结构

高级设计与分析技术

动态规划

与分治类似,通过组合子问题求解原问题,但动态规划应用于子问题重叠的情况(这种情况用分治会反复求解公共子问题)。

步骤:

  1. 刻画最优解的结构特征
  2. 递归定义最优解的值
  3. 计算最优解的值,采用自底向上的方法
  4. 利用计算出的信息构造最优解

钢条问题

=_=

矩阵链乘法

=_=

贪心算法

摊还分析