001什么是時間復雜度？

時間復雜度指執行這個算法需要消耗多少時間，也可以認為是對排序數據的總的操作次數。常見的時間復雜度有：常數階O(1),對數階O(log2n),線性階O(n), 線性對數階O(nlog2n),平方階O(n2)。

//時間復雜度O(1)
sum = n*(n+1)/2; 
//時間復雜度O(n)
for(int?i = 0; i < n; i++){ 
    System.out.println("%d ",i);
} 
//時間復雜度O(n^2)
for(int?i = 0; i < n; i++){ 
    for(int?j = 0; j < n; j++){ 
        System.out.println("%d ",i); 
    }
} 
//運行次數為(1+n)*n/2//時間復雜度O(n^2)
for(int?i = 0; i < n; i++){ 
    for(int?j = i; j < n; j++){ 
        System.out.println("%d ",i); 
    }
} 
//設執行次數為x. 2^x = n 即x = log2n,時間復雜度O(log2n)
int?i = 1, n = 100;
while(i < n){ 
    i = i * 2;
}

002常見的時間復雜度排序?

O（1）< O（logn）<O（n）<O（nlog2n）<O（n2）<O（n3）<…<O（2n）<O（n!）

003空間復雜度是什么？

空間復雜度是指算法在計算機內執行時所需存儲空間的度量，它也是問題規模n的函數

常見的空間復雜度有：常量空間復雜度O(1)、對數空間復雜度O(log2N)、線性空間復雜度O(n)。

004時間復雜度和空間復雜度關系？

對于一個算法來說，空間復雜度和時間復雜度往往是相互影響的。當追求一個較好的時間復雜度時，可能會使空間復雜度的性能變差，即可能導致占用較多的存儲空間；反之，當追求一個較好的空間復雜度時，可能會使時間復雜度的性能變差，即可能導致占用較長的運行時間。有時我們可以用空間來換取時間以達到目的。

005什么是算法穩定性？

假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的。排序算法是否為穩定的是由算法具體實現決定的。總體上，堆排序、快速排序、希爾排序、直接選擇排序不是穩定的排序算法，而冒泡排序、直接插入排序、歸并排序、基數排序、計數排序、桶排序是穩定的排序算法。

006比較排序和非比較排序的區別？

比較類排序：通過比較來決定元素間的相對次序，由于其時間復雜度不能突破O(nlogn)，因此也稱為非線性時間比較類排序。如冒泡排序、選擇排序、插入排序、歸并排序、堆排序、快速排序

非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運行，因此也稱為線性時間非比較類排序。 如計數排序、基數排序、桶排序

007十大排序的復雜度及穩定性？

008下列哪種排序算法不是穩定的？

A. 基數排序
B. 冒泡排序
C. 選擇排序
D. 歸并排序
答案：C
解析：選擇排序是不穩定的，如{2*，2,1}，第一次遍歷將2*與1互換，結果為{1,2,2*}，2與2*位置互換
其余排序均是穩定的

009在各自最優條件下,對N個數進行排序,哪個算法復雜度最低的是? （）

A. 插入排序
B. 快速排序
C. 堆排序
D. 歸并排序
答案：A
解析：插入排序：最佳O（N）
         快速排序：最佳O（NlogN）
         堆    排序：最佳O（NlogN）
         歸并排序：最佳O（NlogN），因此選擇插入排序。