algorithm

1. 算法理解

递归，分治算法，动态规划和贪心选择的区别

1.1. 分治法与动态规划的相同的区别

1. 分治法与动态规划主要共同点：
   • 二者都要求原问题具有最优子结构性质，都是将原问题分而治之，分解成若干个规模较小(小到很容易解决的程序)的子问题。然后将子问题的解合并，形成原问题的解。
2. 分治法与动态规划实现方法：
   1. 分治法通常利用递归求解。
   2. 动态规划通常利用迭代法自底向上求解，但也能用具有记忆功能的递归法自顶向下求解。
3. 分治法与动态规划主要区别：
   1. 分治法将分解后的子问题看成相互独立的。
   2. 动态规划将分解后的子问题理解为相互间有联系，有重叠部分。

1.2. 分治法与二分法的相同的区别

二分算法是比较一次，直接扔掉不符合要求的那一半。（如果中间的不行，则某一边一定不行）
分治不能这么做，它只是做了划分，并没有减小问题规模。（两边分别做，然后整体做一次，其中对整体的操作要求为O(n)复杂度才可以，一般要求两边都要有序，可以在归并排序的思路

2. 递归和迭代

• 迭代与普通循环的区别是：迭代时，循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。
• 递归与普通循环的区别是：循环是有去无回，而递归则是有去有回(因为存在终止条件)。
  在循环的次数较大的时候，迭代的效率明显高于递归。

//递归的实现
int fib(int n){  
    if(n>1) return fib(n-1) + fib(n-2);  
    else return n; // n = 0, 1时给出recursion终止条件  
}  
//迭代的实现
int fib(int n){  
    int i, temp0, temp1, temp2;        
    if(n<=1) return n;  
    temp1 = 0;  
    temp2 = 1;  
    for(i = 2; i <= n; i++){  
        temp0 = temp1 + temp2;  
        temp2 = temp1;  
        temp1 = temp0;  
    }  
    return temp0;  
} 

3. 红黑树和自平衡二叉(查找)树区别

1. 红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。
2. 平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。

AVL树是最早出现的自平衡二叉(查找)树
红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
红黑树和AVL树的区别在于它使用颜色来标识结点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。

红黑树是牺牲了严格的高度平衡的优越条件为代价红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。