T(N)=aN^b 幂次法则
三 数学模型
一个程序运行的总时间主要与两点有关: 执行每条语句的耗时；
执行每条语句的频率。
前者取决于计算机、Java编译器和操作系统，后者取决于程序本身和输入。
排列：
排列公式是建立一个模型，从n个不相同元素中取出m个排成一列（有序），第一个位置可以有n个选择，第二个位置可以有n-1个选择（已经有1个放在前一个位置），则同理可知第三个位置可以有n-2个选择，以此类推第m个位置可以有n-m+1个选择，则排列数A(n m)=n*(n-1)*(n-2)...*(n-m+1)
由阶乘的定义可知A(n m)=[n*(n-1)*(n-2)...*(n-m+1)]*[(n-m)*(n-m-1)...*1]/[(n-m)*(n-m-1)...*1]
上下合并可得A(n m)=n!/(n-m)!
组合：
组合公式对应另一个模型,从n个不相同元素中取出m个排成一列（无序），可以先考虑排列A(n m)，由于m个元素组成的一组可以有m!种不同的排列（全排列A(m m) = m!），所以组合的总数就是A(n m)/m!，即为C(n m) = A(n m)/m! = n![m!(n-m)!]
数学归纳法证明 C(N，3) = N(N-1)(N-2)/6
当N = 3时，cnt = 3*(3-1)*(3-2)/6 = 1成立
当N=4，5，6......N时，cnt(N) = N(N-1)(N-2)/6 均成立。
则当N=N+1时，先取其中N个数，可以有cnt(N)，
再从这N个数中取两个数与余下一个组合，则共有N(N-1)/2（排列组合），
所以cnt(N+1) = cnt(N) + N(N-1)
『大O』：这种在描述算法性能的渐进上限时十分有用，这在算法理论领域十分重要，但在预测算法性能或是比较算法时并没有什么用。（上界）
因为它描述的仅仅是运行时间的上限，而算法的实际性能可能要好的多。一个算法的运行时间可能既是O(N^2)也是~aNlogN的。因此，它不能解释类似倍率实验等测试。
为什么应用这么广泛？
因为它简化了对增长数量级的上限的研究，甚至也适用于一些无法进行精确分析的复杂算法。另外，它还可以和计算理论中用于将算法按照它们在最坏情况下的性能分类的”大Omega”和”大Theta"符号一起使用。
Ω用来表示最坏情况下的性能下限。（最快—下界）
Θ用于描述算法的最佳性能，即不存在有更好的最坏情况下的渐进增长数量级的算法。算法的最优性显然是实际应用中值得考虑的一点，但是还有其他许多因素要考虑。（确界）
为什么都用大O，不用大Θ
我猜想原因之一是我们在执行一个算法的时候往往不知道输入的分布情况。所以考虑最坏情况比考虑一个（假设输入程均匀分布下的）平均资源消耗更有意义。
我猜想另一个原因是，大O，能保证算法可行与否。
3.1 近似
3.5 成本模型
暴力算法：利用枚举所有的情况，或者其它大量运算又不用技巧的方式，来求解问题的方法。
(实现并分析该问题的一种简单的解法。)
总结
五 设计更快的算法
5.1 热身运动 2-sum
分治法：分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
六 倍率实验
6.1 评估它解决大型问题的可行性
6.2 评估使用更快的计算机所产生的价值
七 注意事项
1.大常数
2.非决定性的内循环
3.指令时间
4.系统因素
5.对输入的强烈依赖
6.多个问题参量
八 处理对于输入的依赖
8.5 均摊分析
通过记录所有操作的总成本并除以操作总数来将成本均摊。
九 内存
典型的的Java实现使用8位表示一个字节，用2字节（16位）表示一个char值，用4字节（32位）表示一个int值，用8字节（64位）表示一个double或者long值，用1字节表示一个boolean值（因为计算机访问内存的方式都是一次1字节）
9.1 对象
一个对象所使用的内存量，需要将所有实例变量使用的内存与对象本身的开销（一般是16字节）相加。
这些开销包括一个指向对象的类的引用、垃圾收集信息以及同步信息。
另外，一般内存的使用都会被填充为8字节（64位计算机中的机器字）的倍数。
对象的引用一般都是一个内存地址，因此会使用8字节。
9.2 链表
一个栈需要使用（32+64N）个字节
一个Stack对象32字节，一个node对象40字节，一个Integer对象24字节
9.3 数组
Java中数组被实现为对象，它们一般会因为记录长度而需要额外的内存。
一个原始数据类型的数组一般需要24字节的头信息（16字节的对象开销，4字节用于保存长度以及4字节填充字）再加上保存值所需的内存。
例如，一个含有N个int值的数组需要使用（24+4N）字节（会被填充为8的倍数）
一个含有N个double值的数组需要使用（24+8N）字节
一个对象的数组就是一个对象的引用的数组，所以我们应该在对象所需的内存之外加上引用所需的内存。
例如，一个含有N个Date对象的数组需要使用24字节（数组开销）加上8N字节（所有引用）加上每个对象的32字节，总共（24+40N）字节。
二维数组是一个数组的数组（每个数组都是一个对象）。
例如，一个M*N的double类型的二维数组需要使用24字节（数组的数组的开销）加上8M字节（所有元素数组的引用）加上24M字节（所有元素数组的开销）加上8MN字节（M个长度为N的double类型的数组），总共（8MN+32M+24）~8MN字节。
9.4 字符串对象
String的标准实现含有4个实例变量：一个指向字符数组的引用（8字节）和三个int值（各4字节）。
第一个int值描述的是字符数组中的偏移量。
第二个int值是一个计数器（字符串的长度）。对象所表示的字符串由value[offset]到value[offset+count-1]中的字符组成。
第三个int值是一个散列值，它在某些情况下可以节省一些计算，现在先忽略它。
因此每个String对象总共会使用40字节（16字节表示对象，三个int实例变量各需4个字节，加上数组引用的8字节和4个填充字节）
这是除字符数组之外字符串所需的内存空间，所有字符所需的内存需要另计。
（因为String的char数组常常在多个字符串之间共享）这种设计使String的实现在能够在多个对象都含有相同的value[]数组时节省内存。
9.5 字符串的值和子字符串
一个长度为N的String对象一般需要使用40字节（String对象本身）加上（24+2N）字节（字符数组），总共（64+2N）字节。
当你调用substring()方法时，就创建了一个新的String对象（40字节），但它依然重用了相同的value[]数组，因此该字符串的子字符串只会使用40字节的内存。
网友评论