// 全局變量膳殷，大小為10的數(shù)組array绘雁，長度len，下標i。
int array[] = new int[10];
int len = 10;
int i = 0;
// 往數(shù)組中添加一個元素
void add(int element) {
if (i >= len) { // 數(shù)組空間不夠了
// 重新申請一個2倍大小的數(shù)組空間
int new_array[] = new int[len*2];
// 把原來array數(shù)組中的數(shù)據(jù)依次copy到new_array
for (int j = 0; j < len; ++j) {
new_array[j] = array[j];
}
// new_array復(fù)制給array郑兴，array現(xiàn)在大小就是2倍len了
array = new_array;
len = 2 * len;
}
// 將element放到下標為i的位置坐儿，下標i加一
array[i] = element;
++i;
}
當i < len時, 即 i = 0,1,2,...,n-1的時候律胀，for循環(huán)不走，所以這n次的時間復(fù)雜度都是O(1);
當i >= len時, 即 i = n的時候貌矿，for循環(huán)進行數(shù)組的copy炭菌，所以只有這1次的時間復(fù)雜度是O(n);
由此可知:
該算法的最好情況時間復(fù)雜度(best case time complexity)為O(1);
最壞情況時間復(fù)雜度(worst case time complexity)為O(n);
平均情況時間復(fù)雜度(average case time complexity),
第一種計算方式: (1+1+...+1+n)/(n+1) = 2n/(n+1) 【注: 式子中1+1+...+1中有n個1】,所以平均復(fù)雜度為O(1);
第二種計算方式(加權(quán)平均法，又稱期望): 1(1/n+1)+1(1/n+1)+...+1(1/n+1)+n(1/(n+1))=1逛漫，所以加權(quán)平均時間復(fù)雜度為O(1);
第三種計算方式(均攤時間復(fù)雜度): 前n個操作復(fù)雜度都是O(1)黑低，第n+1次操作的復(fù)雜度是O(n)，所以把最后一次的復(fù)雜度分攤到前n次上酌毡，那么均攤下來每次操作的復(fù)雜度為O(1)
