第一题 递推式 T(n)=2T(n-1)+1

第一步：不要急着套公式

很多同学一看到递推式，就想到 Master 定理。

但是 Master 定理只适用于

T(n)=aT(n/b)+f(n)

例如

T(n)=2T(n/2)+n

而本题是

T(n)=2T(n-1)+1

这里不是

n 变成 n/2

而是

n 变成 n-1

所以Master 定理不能使用！

第二步：不断展开

这是解决这种题目的最好办法。

原式

T(n)=2T(n-1)+1

继续展开

第一次：

T(n) =2[ T(n-1) ] +1

把

T(n-1)

继续展开

=2[2T(n-2)+1]+1

整理

=4T(n-2)+3

继续展开

=4[2T(n-3)+1]+3

得到

=8T(n-3)+7

再展开

=16T(n-4)+15

大家发现规律了吗？

第三步：寻找规律

展开几次后：

T(n)=2T(n-1)+1 T(n)=4T(n-2)+3 T(n)=8T(n-3)+7 T(n)=16T(n-4)+15

整理一下

观察常数

1 3 7 15

是不是

2¹-1 2²-1 2³-1 2⁴-1

所以可以猜到

展开 k 次后

T(n) =2^k T(n-k) +(2^k-1)

第四步：一直展开到底

什么时候停止？

一直展开到

T(1)

即可。

此时

k=n-1

于是

T(n) =2^(n-1)T(1) +2^(n-1)-1

由于

T(1)

只是一个常数。

例如

T(1)=1

那么

T(n) =2^(n-1) +2^(n-1)-1 =2^n-1

于是

时间复杂度就是

O(2^n)

第五步：为什么是指数级？

我们画递归树更容易理解。

第一层

T(n)

第二层

T(n-1) T(n-1)

因为前面有

2

于是出现两个。

第三层

每个又变成两个。

于是

4个

第四层

8个

第五层

16个

整个递归树就是

T(n) / \ T(n-1) T(n-1) / \ / \ T(n-2)... T(n-2)...

每下降一层

节点数量乘2。

高度约

n

因此总节点数

1+2+4+8+... ≈2^n

所以复杂度就是

O(2^n)

七级竞赛中常见递推复杂度总结

第2题 唯一分解定理

答案：D

这题考的是基础知识。

什么叫唯一分解定理？

任何大于1的整数

都可以写成

若干质数相乘

例如

12 =2×2×3

18

2×3×3

60

2×2×3×5

而且

这种分解方式唯一。

A为什么正确？

如果已经知道

每个数最小质因子

例如

12 最小质因子2

那么

12 ↓ 2 ↓ 6 ↓ 2 ↓ 3 ↓ 结束

一次一次除即可。

因此非常快。

B为什么正确？

欧拉筛为什么快？

因为

每个合数 只会被最小质因子筛掉一次

例如

12

不会被

3 4 6

重复处理。

因此

O(n)

C为什么正确？

假设

91

如果

2 3 5 7

都不能整除。

而

√91≈9

那么

说明它没有小质因子。

根据唯一分解定理

它一定是质数。

D为什么错误？

埃氏筛（埃拉托斯特尼筛）

为什么是

O(nloglogn)

主要原因是

不断标记倍数

不是因为唯一分解定理。

所以

D错。

第3题 最长公共子序列（LCS）

答案：B

题目说：

LCS=5

什么叫公共子序列？

例如

ABCDEF AEDCF

公共子序列可以是

ACF

不用连续。

为什么B正确？

既然

最长公共子序列长度=5

说明

至少

有5个字符能够匹配。

因此

至少有5个公共字符

正确。

A为什么错？

编辑距离

和

LCS

关系是

编辑距离≠LCS

不能直接推出。

C为什么错？

公共子串要求

连续

公共子序列

不用连续

完全不是一个概念。

例如

ABCDE AXBYCZDE

LCS

ABCDE 长度5

最长公共子串只有

DE

长度2。

D为什么错？

两个串长度完全可以不同。

例如

ABCDE XXABCDEYY

LCS

还是5。

第4题 树的度数之和

答案：B

树有一个重要性质：

边数=n-1

每条边连接两个点。

所以

度数总和 =2×边数 =2(n-1)

因此答案就是

2n-2

为什么？

例如

1 | 2 / \ 3 4

边数

3

度数

1 3 1 1

加起来

6 =2×3

永远成立。

考试一定要记住

树 边=n-1 度数和=2(n-1)

属于必考公式。

第5题 哈希表

答案：D

题目问

错误的是哪一个。

A正确

装载因子

元素个数/桶数

越大

说明越挤。

冲突自然越多。

B正确

开放定址删除

不能直接删。

否则查找链断掉。

因此一般要

删除标记

实现复杂。

C正确

链地址法

最坏情况

所有元素进一个桶。

变成链表。

复杂度

O(n)

D错误

很多同学最容易掉坑。

哈希表

平均

O(1)

不是

总是O(1)

如果发生大量冲突

仍然可能

O(n)

所以D错误。

第6题 Kruskal算法

答案：B（贪心）

Kruskal流程：

第一步

排序

最小边 ↓ 第二小 ↓ 第三小

第二步

依次加入。

第三步

如果形成环

跳过。

否则加入。

为什么叫贪心？

因为

每一步

都选择

当前最便宜

并且希望最终也是最优。

这就是

Greedy

常见算法分类：

第7题 二分答案（奶牛放置问题）

答案：B（3）

这是竞赛中的经典模型——二分答案 + 贪心检验。

第一步 排序

数组

1 2 8 4 9

排序后

1 2 4 8 9

第二步 二分答案

搜索

最小间距dist

初始

l=0 r=8

第一次

mid=(0+8+1)/2 =4

尝试距离4。

放牛：

第一头

1

第二头

>=5 8

第三头

>=12 没有

只能放2头。

失败。

r=3

第二次

l=0 r=3 mid=2

放牛

1 4 8

成功。

l=2

第三次

mid=3

放牛

1 4 8

仍成功。

l=3

结束。

答案

3

为什么check()使用贪心？

check()总是尽量把下一头牛放在最靠前且满足距离要求的位置。这样能为后面的牛留下尽可能多的空间，因此如果这种放法都放不下k头牛，其他放法也不可能成功。这就是二分答案中常见的“贪心验证”。

第一部分（1~7题）知识点总结

这7道题几乎覆盖了七级算法竞赛中的核心基础：