算法(2)

一、栈和队列

　　1.定义：

　　2.操作：入栈/队列、出栈/队列、判断满/空

　　3：空间复杂度：O(n)

　　4：单次操作的时间复杂度：O(1)

　　5:区别：

　　　　(1)先进先出(FIFO)

　　　　(2)先进后出FILO

　　6：数组和链表皆可(线性表)

　　　　指针(辅助变量)

　　　　　　栈顶/底指针

　　　　　　队头/尾指针

　　　　关键：出入元素同时移动指针

　　7：栈的应用：括号匹配检测

　　　　括号、引号等符号是成对出现的，必须相互匹配

　　　　设计一个算法，自动检测输入的字符串中的括号是否匹配

　　8.栈的应用：模拟栈系统

　　9.快排最坏的空间复杂度是多少？怎么优化空间复杂度？

　　10.作业题：设计一个栈/队列

　　　　　　支持：出、如，求最大元素

　　　　　　要求所有操作O(1)

　　　　　　一个例子：

1 in ,4 in ,2 in ,5 in ,out,out,6 in,out,out,out

int F(int n){　　　　　　　　　　
     if(n<=1)
           return 1;    
}    return n*F(n-1);

　　

do{
           if(!back){
                    if(n<=1){
                            back=true,ret=1;
                            continue;
     }  

}  
n进栈
--n;
}else{ret*=出栈；
}while(栈不为空)    

二、并查集

　　1.定义：存放数据的集合关系，如{1,2}  {3,4}   {5}

　　2.支持操作

　　　　(1)建立新集合

　　　　(2)查找某个元素属于哪个集合

　　　　(3)合并两个集合

　　3.均摊时间复杂度近似为O(1)

　　4.并查集的应用

　　　　(1)假设n个节点，初始的时候点与点之间没有连接

　　　　(2)给出一系列的连接操作

　　　　(3)一次连接操作不产生环，则接受，否则被抛弃

　　5.存储：使用数组标记每个元素的子集

　　6.合并：直接将根节点属于的子集改变

　　7.查找：从带查找节点倒推到根节点

　　8.优化：路径压缩

　　9.作业(1):编写快速排序(递归版)

　　　　　(2)将上述代码改为非递归

　　　　　(3)实现并查集的例题

　　　　   (4)进行正确的测试以及压力测试

　　　　　(5)路径压缩优化前后的效率对比

三、哈希表：定义

　　1.存放数据的集合

　　2.操作：根据(key,value)进行

　　　　　　插入，查找，删除(可以没有)

　　3.空间复杂度：O(m)

　　4.单次操作的时间复杂度：O(1)

　　5:本质：key的索引

　　6.给出n个[0,m)范围内的整数，去重

　　7.快速排序

　　　　(1)期望时间复杂度O(nlogn)

　　　　(2)附加空间复杂度O(1)

　　8.计数排序(基数)

　　　　(1)时间复杂度   O(n+m)   超越比较排序下限

　　　　(2)附加空间复杂度   O(m)