前言

今天來寫寫資料結構的題目

1. 證明 3＋9＋27…＋3^N＝O(3^N) (10%)
   證明：
   3＋9＋27＋…＋3^N＝3^1＋3^2＋3^3…＋3^N
   ＝3^N＋3^N＋3^N…＋3^N ＝ N×3^N，for N>=1

f(N)＝3＋9＋27＋…＋3^N ＝ Σ3^I，for 0 <= I <=N ,
令 g(N)＝3^N , c＝N, n0＝1, 則 f(N) <= cg(N) for all N>=1，故時間複雜度為O(3N )

2. A 為二維的陣列(array)，A[3][2]的位址為1936，A[2][3]的位址為1908，假設每一個元素 4 bytes，則 A 的行(column)數是多少？
   提示：請先判斷陣列是以列序或行序儲存。
   A[2][3]的位址在A[3][2]之前，為列序。假設有 n 行，則

(1) 1936＝α＋ 4 × (3n＋2)
(2) 1908＝α＋ 4 × (2n＋3)
(1)－(2) 28＝4n－4
n＝ 8