GESP-C++五级 题库
下述C++代码实现了快速排序算法,最坏情况的时间复杂度是( )。
现在用如下代码来计算xn(n个x相乘),其时间复杂度为( )。
小杨采用如下双链表结构保存他喜欢的歌曲列表:
小杨想在头指针为 head 的双链表中查找他喜欢的某首歌曲,采用如下查询函数,该操作的时间复杂度为( )。
该查询函数的时间复杂度为O(n),其中n是双链表中节点的数量。
函数使用一个指针temp从头指针head开始,沿着双链表向后遍历。
在每个节点处,它检查节点中的歌曲名称是否与目标歌曲my_song匹配。
最坏情况下,如果目标歌曲不在双链表中或者在最后一个节点才找到,那么需要遍历整个双链表,因此时间复杂度为O(n)
这是因为在最坏情况下,需要遍历所有n个节点才能确定目标歌曲是否存在。
上题代码的时间复杂度是( )。
linear_sieve 函数的主要执行部分是主循环,(for (int i = 2; i <= n; ++i)):主循环从2到n进行遍历,因此有O(n)次迭代
下面的代码片段用于计算斐波那契数列。该代码的时间复杂度是( )?
在上题的 _binarySearch 算法中,如果 lst 中有 N 个元素,其时间复杂度是( )。
O(N)
O(logN)
O(NlogN)
O(N2)
以下 fib 函数计算第 n 项斐波那契数( fib(0)=0 , fib(1)=1 ),其时间复杂度为为O(n)。
快速排序算法的时间复杂度与输入是否有序无关,始终稳定为 O(n log n)。( )
快速排序的 平均时间复杂度为 O(nlog?n),但最坏情况下退化为 O(n^2)。
其性能与输入数据是否有序及 pivot 选择策略密切相关。
插入排序的时间复杂度总是比快速排序低。
插入排序的时间复杂度为O(n2),快速排序的均摊时间复杂度为O(nlogn),但是快速排序的最坏情况下,时间复杂度也是O(n2)
插入排序有时比快速排序时间复杂度更低。
插入排序在处理少量元素或部分有序数组时,由于其较低的时间复杂度可能比快速排序效率更高,而快速排序通常在处理大规模随机数据时表现更佳
同样的整数序列分别保存在单链表和双向链中,这两种链表上的简单冒泡排序的复杂度相同。( )(2023年12月C++五级)



