第一講 時(shí)空分析
(1)時(shí)間復(fù)雜度
(2)空間復(fù)雜度
第二講 排序算法
n較大 【快速排序】
n較小 【冒泡排序】
n較大 n值較小 【計(jì)數(shù)排序】
取n的最值 【堆排序】
n較大 要求穩(wěn)定性 【歸并排序】
第三講 線性數(shù)據(jù)結(jié)構(gòu)
1.棧
(1)DFS的顯式寫法 => 類似BFS
(2)回溯 => DFS+狀態(tài)還原
【求總方案數(shù)或者最優(yōu)方案問(wèn)題】
2.隊(duì)列
BFS
【求最少操作次數(shù)】
第四講 樹(shù)形結(jié)構(gòu)的應(yīng)用
1.二叉排序樹(shù) O(nlogn)
遞歸構(gòu)造
2.哈夫曼樹(shù) => 堆實(shí)現(xiàn)
3.樹(shù)狀數(shù)組 => 鄰接表
【貌似NOIp超綱】