知识点练习

递归关系式 $T(n) = 2T(n/2) + O(n^2)$ 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？

假设一个长度为 $n$ 的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？（ ）

假设 $n$ 是图的顶点的个数，$m$ 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于 $m=\Theta(n)$ 的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小（）。

现在用如下代码来计算 $x^n$，其时间复杂度为（）。

对于给定的 $n$，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（ ）。

以比较为基本运算，在 n 个数的数组中找最大的数，在最坏情况下至少要做（ ）次运算。

以比较为基本运算，对于 $2n$ 个数，同时找到最大值和最小值，最坏情况下需要的最小的比 较次数为（ ）。

斐波那契数列的定义为： $F_{1}=1$，$F_{2}=1$，$F_{n}=F_{n-1}+F_{n-2}$$(n\geq 3)$ 。现在用如下程序来计算斐波那契数列的第 $n$ 项，其时间复杂度为（ ）。

对一个 $n$ 个顶点、$m$ 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。