对《算法图解》的笔记(14)

1.2

  算法的速度指的并非时间， 而是操作数的增速。
谈论算法的速度时， 我们说的是随着输入的增加， 其运行时间将以
什么样的速度增加。
算法的运行时间用大O表示法表示。
O (log n )比O (n )快， 当需要搜索的元素越多时， 前者比后者快得
越多。
  

第1章　算法简介 code

 'use strict'; function binary_search(list, item) { let low = 0; let high = list.length - 1;  while (low <= high) { let mid = Math.floor((low + high) / 2); let guess = list[mid]; if (guess === item) { return mid;    } if (guess > item) {      high = mid - 1;    } else {      low = mid + 1;    }  }  return null;} const my_list = [1, 3, 5, 7, 9]; console.log(binary_search(my_list, 3)); // 1console.log(binary_search(my_list, -1)); // null 
 <?phpfunction binarySearch($needle, $array) { $low = 0; $high = count($array) - 1; while ($low <= $high) { $middle = floor(($low + $high) / 2); if ($array[$middle] == $needle) { return $middle;    } if ($array[$middle] > $needle) { $high = $middle - 1;    } else { $low = $middle + 1;    }  } return null;}$array = [1, 3, 5, 7, 9];echo binarySearch(3, $array) . "\n";echo binarySearch(-1, $array) . "\n"; 

第2章　选择排序

小结
计算机内存犹如一大堆抽屉。
需要存储多个元素时， 可使用数组或链表。
数组的元素都在一起。
链表的元素是分开的， 其中每个元素都存储了下一个元素的地址。
数组的读取速度很快。
链表的插入和删除速度很快。
在同一个数组中， 所有元素的类型都必须相同（ 都为int、 double
等） 。
 'use strict';// Selection Sort - O(n^2)// Parameter://  1. random array // 1. Finds the smallest value in an arrayfunction findSmallestIndex(array) { var smallestElement = array[0]; // Stores the smallest value var smallestIndex = 0; // Stores the index of the smallest value  for (var i = 0; i < array.length; i++) { if (array[i] < smallestElement) {      smallestElement = array[i];      smallestIndex = i;    }  }  return smallestIndex;} // 2. Sort the arrayfunction selectionSort(array) { var sortedArray = []; var length = array.length;  for (var i = 0; i < length; i++) { // Finds the smallest element in the array  var smallestIndex = findSmallestIndex(array); // Adds the smallest element to new array sortedArray.push(array.splice(smallestIndex, 1)[0]);  }  return sortedArray;} console.log(selectionSort([5, 3, 6, 2, 10])); // [2, 3, 5, 6, 10] 

3.1

  我很喜欢Leigh Caldwell在Stack Overflow上说的一句
话： “如果使用循环， 程序的性能可能更高； 如果使用递归， 程序可能
更容易理解。 如何选择要看什么对你来说更重要。 ”
  

3.2

  编写递归函数时， 必须告诉它何时停止递归。 正因为如此， 每个递归
函数都有两部分： 基线条件 （ base case） 和递归条件 （ recursive
case） 。 递归条件指的是函数调用自己， 而基线条件则指的是函数不再
调用自己， 从而避免形成无限循环。
  

3.4　小结　

  使用栈虽然很方便， 但是也要付出代价： 存储详尽的信息可能占用大量
的内存。 每个函数调用都要占用一定的内存， 如果栈很高， 就意味着计
算机存储了大量函数调用的信息。 在这种情况下， 你有两种选择。
重新编写代码， 转而使用循环。
使用尾递归 。 这是一个高级递归主题， 不在本书的讨论范围内。
另外， 并非所有的语言都支持尾递归
  递归指的是调用自己的函数。
每个递归函数都有两个条件： 基线条件和递归条件。
栈有两种操作： 压入和弹出。
所有函数调用都进入调用栈。
调用栈可能很长， 这将占用大量的内存。
  
  

11.1

4.1-4.2

function say_hello(){
	 //alert(sum([1, 2, 3, 4]))
	//alert(count([1, 2, 3, 4]))
	//alert( max([1, 5, 10, 25, 16, 1]) );
	alert(quicksort([10, 5, 2, 3]));
}
function sum(arr){
     if(arr.length == 0)
		return 0;
	return arr[0] + sum(arr.slice(1));
}
function count(arr){
       if(arr.length == 0)
		return 0;
	return 1 + count(arr.slice(1));
}
function max(arr){
      if(arr.length == 2){
	  return arr[0] > arr[1] ? arr[0] : arr[1];
	}
	var subMax = max(arr.slice(1));
	return arr[0] > subMax ? arr[0] : subMax;
}
function quicksort(arr){
     if(arr.length < 2)
		  return arr;
	var pivot = arr[0];
	var less = arr.slice(1).filter(function(v){ return v <= pivot;});
	var greater = arr.slice(1).filter(function(v){ return v > pivot;});
	return quicksort(less).concat([pivot],quicksort(greater));
}

4.3

5.1

  刚才你就打造了一个“Maggie”！ 你结合使用散列函数和数组创建了一种
被称为散列表 （ hash table） 的数据结构。 散列表是你学习的第一种包
含额外逻辑的数据结构。 数组和链表都被直接映射到内存， 但散列表更
复杂， 它使用散列函数来确定元素的存储位置。
在你将学习的复杂数据结构中， 散列表可能是最有用的， 也被称为散列
映射、 映射、 字典和关联数组。 散列表的速度很快！ 还记得第2章关于
数组和链表的讨论吗？ 你可以立即获取数组中的元素， 而散列表也使用
数组来存储数据， 因此其获取元素的速度与数组一样快。