超超不会飞

0%

《Algorithms Unlocked》读书笔记1——循环和递归

Posted on Views: Valine:

《Algorithms Unlocked》是 《算法导论》的合著者之一 Thomas H. Cormen 写的一本算法基础。

书中没有涉及编程语言，直接用文字描述算法，我用 JavaScript 对书中的算法进行描述。

循环和查找

首先是三个简单的查找。目的是从数组中查找一个特定的值。

array: 一个数组

x: 要查找的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 简单的线性查找
function linearSearch(array, x) {
  let answer = 'NOT-FOUND';

  for (let i = 0; i < array.length; i++) {
    if (array[i] === x) {
      // 虽然找到了i, 但没有返回继续查找，直到 for 结束
      answer = i;
    }
  }

  console.log(answer);
  return;
}

虽然找到了目标值，但for循环依然继续遍历直到结束，下面是优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 优化的查找，找到目标后立刻返回
function betterLinearSearch(array, x) {

  for (let i = 0; i < array.length; i++) {
    if (array[i] === x) {
      // 直接返回
      console.log(i);
      return;
    }
  }

  console.log('NOT-FOUND');
  return;
}

还有一个问题是：假如直到最后都没有找到目标值，将试图访问越过数组末尾的元素。书上说：“在计算机程序中，当你试图访问越过数组末尾的元素时，结果通常是糟糕的。你的程序可能会崩溃，也可能会损坏数据。”

宁可信其有，不可信其无啊。继续优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 更优的写法
// 总是让 for 循环可以结束
function sentinelLinearSearch(array, x) {
  let n = array.length - 1; // 最后一个元素

  // 把数组最后一个值保存到last变量中
  let last = array[n]
  // 把数组最后一个值替换成目标值
  array[n] = x;
  
  // 判断数组中是否有目标值x，即使没有，数组的最后一个值也一定是目标值，避免越过数组末尾的访问
  let i = 0;
  while (array[i] !== x) {
    i++;
  }

  //如果i小于数组长度，或者最后一个值为目标值x，则返回i
  array[n] = last;
  if (i < n || last === x) {
    console.log(i);
    return;
  }

  return 'NOT-FOUND';
}

第三个方案在进行循环遍历的时候只进行了一个判断——array[i]是否等于x，而上面的两种方案在进行for循环时都要进行i是否大于length的判断和array[i]是否等于x两个判断。所以当数组大到一定程度的时候，第三个方案效率大于上面两个方案。

递归

递归是指在函数中对函数自身进行调用。

递归有两个特性：

  1. 必须有一个或对个基础情况，它是指不用递归而直接计算出结果。比如下面例子中：当 n=0 时，基础情况发生，f(0) = 1;
  2. 程序中的每个递归调用一定是通过一系列关于同一个问题的子问题的求解而最终迭代到基础情况。

下面是一个经典的递归例子，计算阶乘。

当n=0时，n! = 1 且 n! = n(n-1)(n-2)…3•2•1 (n≥0)

比如：5! = 5•4•3•2•1 = 120

1
2
3
4
5
6
7
8
9
// 阶乘
function factorial(n) {
  if (n >= 0) {
    if (n === 0) {
      return 1;
    };
    return n * factorial(n - 1);
  };
}

之前的查找算法也可以写成递归风格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 线性查找的递归风格
function recursiveLinearSearch(array, i, x) {

  if (i < array.length) {
    if (array[i] === x) {
      console.log(i);
      return;
    }else {
      return recursiveLinearSearch(array, i+1, x);
    }
  }

  console.log('NOT-FOUND');
  return;
}