每日一题|复杂度分析你会了吗(第一天)
数据结构
1. 读取一维数组第i个位置上的平均时间复杂度为。 [华中科技大学2019年]
A．O(nlogn)
B．O(n2)
C．O(n)
D．O(1)
2.一个栈的输入序列为123...n，若输出序列的第一个元素是n，输出的第i（1<=i<=n）个元素是< span=""> [中山大学1999]
A. 不确定
B. n-i
C. i
D. n-i+1
请先投票在看解析！
感谢参与投票：
第一题解析：
首先，这是一道复杂度分析的基础题目，一般会出现在选择题的1、2题左右。好，数组本质上是一种特殊的线性表，它的逻辑结构连续、物理结构也连续。也就是说，在申明数组时会在内存中分配一段连续的存储空间，存储数据时按照地址顺序存储。因此，数组具有随机存取的特性。所以，我们可以利用数组下标来获取第i个位置的数据，平均只用访存一次，时间复杂度为O（1）。
第二题解析：
栈的特点为FILO “first in last out”，从题目得知出栈的第一个元素为n，即n为栈顶元素。结合栈的特性，我们可以得知入栈序列从1到n，输出的第一个元素为n，则其余所有元素必定仍在堆栈中。则第2个输出元素为n-1，第3个输出元素为n-2，归纳得知第i个输出元素为n-i+1。
如果您“在看”，请点一下旁边的在看，点一下哦！点在看好运翻倍！！
评论