每日一題|復雜度分析你會了嗎(第一天)

數(shù)據(jù)結(jié)構(gòu)

1. 讀取一維數(shù)組第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

請先投票在看解析！

感謝參與投票：

一定要先自己思考做完后再看解析哦

第一題解析：

首先，這是一道復雜度分析的基礎(chǔ)題目，一般會出現(xiàn)在選擇題的1、2題左右。好，數(shù)組本質(zhì)上是一種特殊的線性表，它的邏輯結(jié)構(gòu)連續(xù)、物理結(jié)構(gòu)也連續(xù)。也就是說，在申明數(shù)組時會在內(nèi)存中分配一段連續(xù)的存儲空間，存儲數(shù)據(jù)時按照地址順序存儲。因此，數(shù)組具有隨機存取的特性。所以，我們可以利用數(shù)組下標來獲取第i個位置的數(shù)據(jù)，平均只用訪存一次，時間復雜度為O（1）。

第二題解析：

棧的特點為FILO “first in last out”，從題目得知出棧的第一個元素為n，即n為棧頂元素。結(jié)合棧的特性，我們可以得知入棧序列從1到n，輸出的第一個元素為n，則其余所有元素必定仍在堆棧中。則第2個輸出元素為n-1，第3個輸出元素為n-2，歸納得知第i個輸出元素為n-i+1。

如果您“在看”，請點一下旁邊的在看，點一下哦！點在看好運翻倍??！