发表于 | 更新于 | 分类于

使二叉树成为二叉查找树的性质是，对于树中的每个节点x,它的左子树中所有项值小于x中的项，而它的右子树中所有项的值大于x中的项。

二叉查找树中的删除
如果节点是一片树叶，那么它可以被立即删除。如果节点有一个儿子，则该节点可以在其父节点调整自己的链以绕过该节点后被删除。

复杂的情况是处理具有两个儿子的节点。一般的删除策略是用其右子树的最小的数据代替该节点的数据并递归地删除那个节点。因为右子树中的最小的节点不可能有左儿子，所以第二次remove要容易。

发表于 | 更新于 | 分类于

队列也是表，使用队列时插入在一端进行而删除在另一端进行。

队列的数组实现

对于每一个队列数据结构，我们保留一个数组theArray以及位置front和back，它们代表队列的两端。我们还要记录实际存在于队列中的元素的个数currentSize。

为使一个元素x入队(即执行enqueue)，我们让currentSize和back增1，然后置theArray[back] = x。若使元素dequeue(出队)，我们置返回值为theArray[front]，且currentSize减1，然后使front增1。

发表于 | 更新于 | 分类于

散列是一种用于以常数平均时间执行插入、删除和查找的技术。但是，那些需要元素间任何排序信息的树操作将不会得到有效的支持。因此，诸如findMin、findMax以及以线性时间将排过序的整个表进行打印的操作都是散列所不支持的。

每个关键字被映射到从0到TableSize - 1这个范围中的某个数，并且被放到适当的单元中。这个映射就叫做散列函数。因为单元的数目是有限的，而关键字实际上是用不完的。因此，我们寻找一个散列函数，该函数要在单元之间均匀地分配关键字。剩下的问题就是要选择一个函数，决定到两个关键字散列到同一个值的时候(冲突)应该做什么以及如何确定散列表的大小。
散列函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int hash(String key, int tableSize)
	{
		int hashVal = 0;
		
		for(int i = 0; i < key.length(); i++)
		{
			hashVal = 37 * hashVal + key.charAt(i);
		}
		
		hashVal %= tableSize;
		if(hashVal < 0)
		{
			hashVal += tableSize;
		}
		return hashVal;
	}

解决冲突
分离链接法

将散列到同一个值的所有元素保留到一个表中。
开放定址法

另有一种不使用链表解决冲突的方法是尝试另外一些单元，直到找出空的单元为止。更常见的是，单元h0(x),h1(x),h2(x),…相继被试选，其中hi(x) = (hash(x) + f(i)) mod tableSize，且f(0) = 0。函数f是冲突解决方法。因为所有数据都要置入表内，所以这种解决方案所需要的表要比分离链接散列的表大。

发表于 | 更新于 | 分类于

基于条件期望的预测

我们关心的是根据t期观测到的一组变量$X_t$预测变量$Y_{t+1}$。
令$Y^_{t+1|t}$表示根据$X_t$作出的对$Y_{t+1}$的预测。为了评价这个预测有用性，我们需要给出一个损失函数来表示当我们的预测偏离一个特定的量时我们的关心程度。通过假定一个二次损失函数，可以得到一个便利的结果。二次损失函数的含义是选择合适的$Y^{t+1|t}$，使得
$$MSE(Y^*{t+1|t})\equiv E(Y_{t+1} - Y^_{t+1|t})^2$$
最小。MSE被称作预测值$Y^_{t+1|t}$的均方误差。
可以证明对该均方误差最小时的预测就是$X_t$条件下$Y_{t+1}$的期望，即：
$$Y^*{t+1|t} =E(Y{t+1}|X_t)$$

基 于线性投影的预测

我们现在将所考察的预测$Y^_{t+1|t}$限定为$X_t$的线性函数：
$$Y^_{t+1|t} = \alpha^,X_t$$
假定我们求出一个$\alpha$值，使得预测误差($Y_{t+1} - \alpha^,X_t$)与$X_t$无关：
$$E[(Y_{t+1} - \alpha^,X_t)X^,_t] = 0^,$$
那么，则预测$\alpha^,X_t$称为$Y_{t+1}$关于$X_t$的线性投影。

发表于 | 更新于 | 分类于

优先队列

在多用户环境中，操作系统调度程序必须决定在若干进程中运行哪个进程。一般说来，短的作业要尽可能快地结束，这一点很重要，因此在已经运行的作业当中这些短作业应该拥有优先权。此外，有些作业虽不短小但很重要，也应该拥有优先权。
这种特殊的应用似乎需要一类特殊的队列，我们称之为优先队列。
优先队列至少允许下列两种操作，

  1. 插入
  2. 删除最小者：找出、返回并删除优先队列中最小的元素。

二叉堆

二叉堆的使用对于优先队列的实现相当普遍。在这里，我们把二叉堆只叫做堆。
像二叉查找树一样，堆也有两个性质，即结构性和堆序性。对堆的操作可能破坏者两个性质中的一个，因此，堆的操作必须到堆的所有性质都被满足时才能终止。

  1. 结构性质
    堆是一棵被完全填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。
    一个重要的观察发现，因为完全二叉树这么有规律，所以它可以用一个数组表示而不需要使用链。
    对于数组中任意位置i上的元素，其左儿子在位置2i上，右儿子在左儿子后的单元(2i + 1)中，它的父亲则在位置[i / 2]上，
  2. 堆序性
    让操作快速执行的性质是堆序性质。由于我们想要快速找出最小元，因此最小元应该在根上。如果我们考虑任意子树也应该是一个堆，那么任意节点就应该小于它所有后裔。

发表于 | 更新于 | 分类于

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶。

栈又叫做LIFO(后进先出表)，由于栈是一个表，因此任何实现表的方法都能实现栈。

栈的链表实现

栈的第一种实现方法是使用单链表。通过在表的顶端插入来实现push，通过删除表顶端元素实现pop。top操作只是考察表顶端元素并返回它的值。

栈的数组实现

与每个栈相关联的操作是theArray和topOfStack，对于空栈它是-1。为将某个元素x推入栈，我们使topOfStack增1然后置theArray[topOfStack] = x。为了弹出栈元素，我们置返回值为theArray[topOfStack]然后使topOfStack减1。

发表于 | 更新于 | 分类于

排序算法除了要考虑时间，空间复杂度以外，还需要考虑到稳定性。

稳定的排序算法表示在排序前后，相等的两个值的前后位置保持不变。

选择排序

首先从第一个元素开始扫描整个序列，并将序列的最小元素和第一个元素交换，然后从第二个元素开始扫描，将n-1个元素中的最小序列与第二个元素交换，执行到n-1个元素后，这个序列就排序好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 升序
 * 遍历数组找出最小的与第一个交换，第二小的与第二个交换...
 * @param originalArr
 * @return
 */
@Override
public int[] asc(int[] originalArr){
    for(int i = 0; i < originalArr.length; i++){
        int min = i;
        for(int j = i+1; j < originalArr.length; j++){
            if(originalArr[min] > originalArr[j]){
                min = j;
            }
        }
        
        int tmp = originalArr[min];
        originalArr[min] = originalArr[i];
        originalArr[i] = tmp;
    }
    return originalArr;
}

冒泡排序

比较相邻的两个元素，如果第一个元素大于第二个元素就交换位置，第一遍最大值将会交换到最后一个位置，第二次循环将n-1个元素中的最大值交换到最后第二个位置，重复操作n-1遍后，这个序列就排序好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 升序
 * 比较相邻元素，将大元素沉下去
 */
@Override
public int[] asc(int[] originalArray) {
    for(int i = 0; i < originalArray.length; i++){
        for(int j = i + 1; j < originalArray.length; j++){
            if(originalArray[i] > originalArray[j]){
                int temp = originalArray[i];
                originalArray[i] = originalArray[j];
                originalArray[j] = temp;
            }
        }
    }
    return originalArray;
}

发表于 | 更新于 | 分类于

考察下面的ARMA模型:
$$Y_t = c + \phi_1 Y_{t-1} + \phi_2 Y_{t-2} + … + \phi_p Y_{t-p} +\epsilon_t + \theta_1\epsilon_{t-1} + \theta_2\epsilon_{t-2} + … + \theta_q\epsilon_{t-q}$$
如何运用Y的观测值来估计$(c,\phi_1,…,\phi_p,\theta_1,…,\theta_q,\sigma^2)$的值。

估计所根据的基本原则是最大似然估计。
从理论上讲，求最大似然估计包括两个步骤。

  1. 计算似然函数式
  2. 求使得这个函数值最大的$\theta$值

令$\theta \equiv (c,\phi_1,…,\phi_p,\theta_1,…,\theta_q,\sigma^2)^,$表示总体参数向量。假定我们观测到一个样本量为T的样本$(y_1,y_2,…,y_T)$，计算概率密度
$$f_{Y_T,Y_{T-1},…,Y_1}(y_T,y_{T-1},…,y_1;\theta)$$
它可近似地看作已观测到的这个具体样本的概率。$\theta$的最大似然估计是使这个具体样本最可能观测到的值，即使式最大的$\theta$值。

发表于 | 更新于 | 分类于

差分方程

所谓差分方程即将变量$y_t$与它的滞后期联系起来的表达式。
研究变量在第t期的值记为$y_t$。假定给出的动态方程将变量y第t期的值与另外的变量$w_t$以及y的前一期联系起来:
$$y_t=\phi y_{t-1}+w_t$$
上述称为一阶差分方程是因为仅仅只有变量的一阶滞后($y_{t-1}$)出现在方程中。

移动平均

“移动平均”的含义源于$Y_t$是最近两期的$\epsilon$的加权平均。
令{$\epsilon_t$}是一个白噪声序列。
$$Y_t = \mu + \epsilon_t + \theta\epsilon_{t-1}$$
其中$\mu$和$\theta$可以是任意的常数。这个时间序列称为一阶移动平均过程，记为MA(1).

自回归过程

一阶自回归过程

一个一阶自回归，记作AR(1)满足下面的差分方程
$$Y_t = c + \phi Y_{t-1} + \epsilon_t$$
{$\epsilon_t$}是一个白噪声序列。

####p阶自回归过程
一个p阶自回归，记作AR(p)满足下式
$$Y_t = c + \phi_1 Y_{t-1} + \phi_2 Y_{t-2} + … + \phi_p Y_{t-p} +\epsilon_t$$

混合自回归移动平均过程

一个ARMA(p,q)过程包括自回归和移动平均项：
$$Y_t = c + \phi_1 Y_{t-1} + \phi_2 Y_{t-2} + … + \phi_p Y_{t-p} +\epsilon_t + \theta_1\epsilon_{t-1} + \theta_2\epsilon_{t-2} + … + \theta_q\epsilon_{t-q}$$