May 20, 2021

20210520

恋词U20 | 数据结构-算法分析补充 | GS2-C6-REW

Table of Contents

恋词U20
数据结构-算法分析补充
GS2-C6-REW

啊今天是520哈~

恋词U20

背完这个单元就进入低频词汇了，之前都是中高频词汇。

capital n.首都；大写字母 adj.死刑的
capitalism n.资本主义（制度）
demolition n.摧毁；拆毁；拆除；大败；击退
interplay n.相互影响，相互作用
playhouse n.剧院；儿童游戏房
counsel v.劝告；提议 n.劝告；忠告
council n.委员会；地方议会；管理委员会
parliament n.国会；议会
ballet n.芭蕾舞；芭蕾舞剧；芭蕾舞团
repertoire n.节目；全部剧目；保留剧目；全部技能
leakage n.泄露；漏
misuse v.n 误用；滥用；苟待
domestic adj.家的；家庭的；国内的；本国的；驯养的；家用的
rein n.缰绳；统治；支配 v.驾驭；控制；统治
monarchy n.君主政体；君主制；皇室；王侯
monarch n.帝王；君主
hierarchy n.等级制度；统治集团
reign v.统治；起支配作用
realm n.王国；国度；领域
throne n.王位；君权
sovereign adj.独立的；有主权的 n.君主；国王
circuit n.巡回；环行
hence adv.从今以后；因此
hitherto adv.到目前为止；迄今
radical adj.基本的；根本的；极端的；激进的
radiant adj.容光焕发的，喜气洋洋的；
radar n.雷达
pearl n.珍珠
summit n.最高点；山顶；顶点；峰会
nuisance n.讨厌的人；讨厌的东西
chamber n.房间；室

数据结构-算法分析补充

线性结构相关时间复杂度分析

顺序表

访问	顺序查找	插入	删除
$O(1)$	$O(n)$	$O(n)$	$O(n)$

链表

访问	顺序查找	插入	删除
$O(n)$	$O(n)$	$O(1)$	$O(1)$

二叉树递归遍历

void r(BTNode *p)
{
    if(p != NULL)
    {
        visit(p);
        r(p->lChild);
        r(p->rChild);
    }
}

时间复杂度：$O(n)$

二叉树非递归遍历

时间复杂度：$O(n)$

二叉树层次遍历时间复杂度

时间复杂度：$O(n)$

非线性结构相关时间复杂度分析

图的邻接矩阵

时间复杂度：$O(n^2)$

图的邻接表

时间复杂度：$O(n+e)$

Prim（普里姆）算法

时间复杂度：$O(n^2)$

Kruskal（克鲁斯卡尔）算法

时间复杂度：$O(eloge)$

Dijkstra（迪杰斯特拉）算法

时间复杂度：$O(n^2)$

Floyd（弗洛伊德）算法

时间复杂度：$O(n^3)$

汉诺塔问题

问题描述与算法引入：

void hanoi(int n, char a, char b, char c)
{
    if(1 == n)
    {
        std::cout<<a<<"->"<<c<<std::endl;
    }
    else
    {
        hanoi(n-1, a, c, b);
        std::cout<<a<<"->"<<c<<std::endl;
        hanoi(n-1, b, c, d);
        
    }
}

时间复杂度分析：时间复杂度：$O(2^n)$

排序算法分析

不在这里解释，参考之前总结的：考研常考排序算法