GESP-C++八级 题库
下列代码的时间复杂度(以 为自变量,忽略常数与低阶项)是( )。
对一个包含V个顶点、E条边的图,执行广度优先搜索,其最优时间复杂度是( )。
O(V)
O(V+E)
O(V^2)
O(E)
下列Dijkstra算法,假设图graph中顶点数v、边数e,则程序的时间复杂度为( )。

O(v^2)
O(vlogv+e)
O(v+e)logv
O(v+e)
下面 count_triple 函数的时间复杂度为( )。

O(n^2)
O(n^2logn)
O(n)
O(nlogn)
n 个结点的二叉树,执行广度优先搜索的平均时间复杂度是?( )
下面的 sum_digit 函数试图求出从 1 到 n (包含 1 和 n )的数中,包含数字 d 的个数。该函数的时间复杂度为?( )
下面 LIS 函数试图求出最长上升子序列的长度,其时间复杂度为?( )
2025 是个神奇的数字,因为它是由两个数 20 和 25 拼接而成,而且 2025 =(20+25)2 。小杨决定写个程序找找小于 N 的正整数中共有多少这样神奇的数字。
该函数的时间复杂度为?( )
下面Floyd算法程序的时间复杂度为?( )
22, 23 ,24 行,循环共执行 o(n3) 次。(图论算法: Floyd 算法)
假设图graph中顶点数v、边数e,上题程序的时间复杂度为( )。
O(e)
O(v2)
O(vlogv+e)
O((v+e)logv)
n个结点的二叉树,执行释放全部结点操作的时间复杂度是( )。
对二叉树执行DFS,在回溯阶段依次释放每个节点,复杂度O(n)。
下面程序的 Merge_Sort 函数时间复杂度为( )。
归并排序基于分治
时间复杂度为O(nlogn)。空间复杂度O(n);
有V个顶点、E条边的图的深度优先搜索遍历时间复杂度为( )。
每个顶点每条边都会被访问一次,所有时间复杂度是C。
下面程序的时间复杂度为( )。
代码是求欧拉筛,参数有些优化,时间复杂度是C。
下面程序的最差时间复杂度为( )。
欧几里得算法的最坏时间复杂度。在最坏的情况,m和n为菲波那切数列中相邻的两项,所以时间复杂度是O(logn)。