每日一题|复杂度分析你会了吗(第一天)

数据结构

1. 读取一维数组第i个位置上的平均时间复杂度为。 [华中科技大学2019年]

A．O(nlogn)

B．O(n­2)

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。

如果您“在看”，请点一下旁边的在看，点一下哦！点在看好运翻倍！！