数据结构基础题型

第一章绪论

1. (2022) 下列程序段的时间复杂度是 ( )。

A. O(log₂n)B. O(n^1/2)C. O(n)D. O(n²)

【分析】

算法复杂度描述，关键语句的执行次数t和问题规模n的关系。

	第1轮	第2轮	第3轮	...	第log₂n轮
i	1	2	4	...	$\frac{n}{2}$
j	0	0,1	0,1,2,3	...	0,1,2,..., $\frac{n}{2}$ -1
t	1	2	4	...	$\frac{n}{2}$

知道每轮的执行次数t，以及共有多少轮log₂n。所有轮循环的执行次数总和：t=(1+2+4+...+ $\frac{n}{2}$ )，形成log₂n项等比数列求和：

t = (1 + 2 + 4 + \dots + \frac{n}{2}) = \frac{a_{1} (1 - q^{n})}{1 - q} = \frac{1 \times (1 - 2^{l o g_{2} n})}{1 - 2} = n .

2. (2025) 下列程序段的时间复杂度是 ( )。

A. O(log₂n)B. O(n^1/2)C. O(n)D. O(n²)

【分析】

	第1轮	第2轮	第3轮	...	第log₂n轮
i	1	2	3	...	$\sqrt{n}$
j	1	1,2	1,2,3	...	1,2,3,..., $\sqrt{n}$
t	1	2	3	...	$\sqrt{n}$

t = (1 + 2 + 3 + \dots + \sqrt{n}) = \frac{(1 + \sqrt{n}) \sqrt{n}}{2} = n .