Reference Datat Types 引用参考数据类型 -> 组合数据类型
Array, Hash和程序员自定义的复合资料类型
组合数据的修改：
组合数据类型的变量，不是直接存值，而是存一个reference引用位置，指向另一块真正存值的内存空间。
因为组合数据类型是个容器，这个容器可能存有非常多的数据，复制的成本是很高的。因此在默认的情况下，我们不会真的去复制它的值，而是复制引用而已。
object_id 方法 显示内存位置
方法调用也必须注意参数是基本类型还是引用类型：
def foo(x)
x = 9999
return x
end
x = 1 foo(x);
x #=> 基本类型外部的局部变量不会被foo方法所改变
但是Reference Data Type则会被改变。
def bar(x) {
x[0] = 9999;
}
arr = [1,2,3];
bar(arr) #=> [999,2,3]
clone方法
组合数据类别的 = 指派只会复制引用，如果需要真的复制值，需要用clone方法。
⚠️ ：Ruby内建的 clone 方法是不支援 deep clone (深度复制，嵌套内的复制)
内建的 clone 是不支援 deep clone,如果真的要复制，你需要自己写方法。
a = [1,2,3]
b = [0, a] c = b.clone
a[0] = 999 b
c
b和c都会变为[0,[999,2,3]]
11 什么是算法？
1960年代发明的Structured programming是一种编程典范，它采用function,程序码区块，循环等结构，来取代传统的goto语法（c语言）。希望借此来改善电脑程序的明晰性，品质以及开发时间，并且避免写出面条式的代码。
现代编程语言的特性： Flow control and function
所谓算法是一种有次序，明确定义和可行，最终会结束，有输出的可执行步骤。
def find_max(arr)
max = arr[0] arr.each do |a|
if a > max
max = a
end
end return max
end
暴力搜寻技术。穷尽可能。
12 评估算法
当数据越来越多，一个算法需要耗费的时间。 Big-O 的符号来描述算法复杂度
def constant(n)
result = n * n
result = result + 1 return result
end
不管n 是多少，执行步骤时间固定，时间复杂度O(1),常数。
def quadratic(n)
sum = 0
1.upto(n) do |i|
1.upto(n) do |j|
sum = sum + i + j
end
end return sum
end
quadratic方法，当n越大，里面的循环就得平方多次，时间复杂度o(n^2)平方的。
def logarithmic(n)
result = 0
while n > 1
n = n.to_f / 2
result += 1
end return result
end
O(logn),对数时间。当n从100变为100000时，时间只是2.5倍而已。
。在数学中，真数 x（对于底数 β）的对数是 βy 的指数 y，使得 x=βy
例子：
-
，
我们可以得出
-
，
用日常语言说，以3为底81的对数是4。
快速排序法，（quick sort）—O(n log n)期望时间，O(n2)最坏情况；对于大的、随机数列表一般相信是最快的已知排序。
Ruby中的 Array#sort 就是用快速排序法。
见笔记http://www.cnblogs.com/chentianwei/p/8244728.html，或者*
13 什么是数据结构
数据结构定义资料之间的相互关系，是设计算法的载体，数据输入输出和设计算法步骤时，都会对应于使用的数据结构。而不同的数据结构有不同的特性。在计算机本科生的课程中，有门数据结构的课，就是在分析各种不同的数据结构，做不同操作时的优点点和复杂度：Common Data Structure Operations
对 Ruby 程序员来说，最常用的就是 Array 和 Hash，现在我们来分析一下常用的操作，对 Array 和 Hash 的算法复杂度。
插入和删除到容器里面
要在数组中插入一个值，如果刚好在最后(例如 Arrar#push 方法)，是 O(1)
如果在数组中间插入一个值，因为数组是内存中「连续」的空间，中间新插入，会需要搬动后面所有元素的位置往后移动一格，这是 O(n) 的算法，n 越大需要移动的元素越多。
对散列 Hash 来说，插入是平均复杂度是 O(1)。
检查一个值都没有在容器里面
Array 是 O(n)，需要走访整个数组依序检查
Hash 是 O(1)，只要将 key 经过散列算法，就可以直接检查那个位置有没有数据。
Ruby 内建有 benchmark 工具，可以让我们量测一个方法的执行时间
还有一道二分算法搜索题。没做。
这门教程的知识点非常多，包括了计算机大学本科 1. 数据结构 2. 算法 3. 操作系统 4. 编译器 5. 编程语言，大一到大三共五门必修课程的主要概念。我推荐以下的书籍可以继续进修：
- 改变未来的九大算法 介绍九个影响世界的重要的算法，没有代码，是科普书
- 一路编程，入门程度的概括性介绍软件编程
- 代码之髓 介绍编程语言的设计
- 程序是怎样跑起来的
- 计算机是怎样跑起来的
- 大话数据结构
- 算法图解
二分搜索：
Ruby 的 Array#find_index 方法可以从数组中寻找一个值，回传它的索引，这个算法是 O(n)。
arr = [5,1,9,6] arr.find_index(9) # 回传 2
Ruby 还有一个 Array#bsearch，实作了 二分搜索算法 binary search。如果你已知数组是排序过的，这个算法会是 O(log n)。
https://gist.github.com/michaelmakun/5a3ac6c03fd386e0629d5f1ed8a10ed1