選擇排序和冒泡排序的空間復(fù)雜度和時(shí)間復(fù)雜度是多少？直接選擇排序和冒泡排序的空間復(fù)雜度為O（1），因?yàn)橹皇褂昧藘蓚€(gè)循環(huán)變量和一個(gè)或兩個(gè)中間變量，如flag和exchange，這與要排序的記錄數(shù)無關(guān)。冒泡

選擇排序和冒泡排序的空間復(fù)雜度和時(shí)間復(fù)雜度是多少？

直接選擇排序和冒泡排序的空間復(fù)雜度為O（1），因?yàn)橹皇褂昧藘蓚€(gè)循環(huán)變量和一個(gè)或兩個(gè)中間變量，如flag和exchange，這與要排序的記錄數(shù)無關(guān)。冒泡排序的時(shí)間復(fù)雜度最好是關(guān)鍵字排序，n-1關(guān)鍵字比較，0記錄移動(dòng)，最差的是完全逆序，n（n-1）/2關(guān)鍵字比較當(dāng)記錄移動(dòng)3N（n-1）/2次時(shí)，冒泡排序的時(shí)間復(fù)雜度為O（n^2）。當(dāng)記錄移動(dòng)至少0次，最多3（n-1）/2次時(shí)，直接選擇排序的時(shí)間復(fù)雜度為O（n^2）

請(qǐng)教，快速排序的空間復(fù)雜度？

快速排序每次將要排序的數(shù)組分成兩部分。在理想情況下，如果要排序的數(shù)組每次被劃分為兩個(gè)等長(zhǎng)的部分，則需要將其劃分logn次。在最壞的情況下，即當(dāng)數(shù)組是有序的或大致有序的時(shí)，每個(gè)分區(qū)只能減少一個(gè)元素，快速排序?qū)⒉恍彝嘶癁槊芭菖判?，因此快速排序的時(shí)間復(fù)雜度下限為O（nlogn），最壞的情況是O（n^2）。在實(shí)際應(yīng)用中，快速排序的平均時(shí)間復(fù)雜度為O（nlogn）。在序列的操作中，快速排序只需要常量空間?？臻g復(fù)雜度為s（1）。但是需要注意的是，遞歸堆棧需要花費(fèi)最少的logn和最多的n個(gè)空間。

如何計(jì)算一個(gè)算法的時(shí)間復(fù)雜度和空間復(fù)雜度？

它是根據(jù)數(shù)據(jù)n的大小來顯示程序所使用的近似時(shí)間和空間

說白了，它是顯示時(shí)間或空間如何隨著n的增長(zhǎng)而增長(zhǎng)

例如

對(duì)于（int i=0 i

這個(gè)循環(huán)執(zhí)行n次，所以時(shí)間復(fù)雜度是O（n）

for（int i=0 i

{

for（int j=0 j

}]這個(gè)嵌套的兩個(gè)循環(huán)，時(shí)間復(fù)雜度是O（n^2）

時(shí)間復(fù)雜度只能粗略地表示所用的時(shí)間

而且一些基本步驟的運(yùn)行時(shí)間是不同的，所以我們無法計(jì)算，所以我們省略了

for（int i）=0I

a=b

and

for（int i=0I

運(yùn)行時(shí)間當(dāng)然是第二快的，但是它們的時(shí)間復(fù)雜度是一樣的堆排序是用堆作為數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的排序算法。Heap是一種幾乎完全的二叉樹結(jié)構(gòu)，它滿足Heap的性質(zhì)：子節(jié)點(diǎn)的鍵值或索引總是小于（或大于）父節(jié)點(diǎn)。堆排序的平均時(shí)間復(fù)雜度為O（nlogn），空間復(fù)雜度為θ（1）。

什么是堆排序呢，其時(shí)間復(fù)雜度是怎么計(jì)算的呢？

時(shí)間復(fù)雜度是程序的運(yùn)行時(shí)間或次數(shù)；

空間復(fù)雜度是程序占用的空間；

以下程序：

int a[1000000

]int CNT=0

for（int i=0 i

for（int j=0 j

a[CNT]=0

空間主要是一個(gè)大小為1000000的數(shù)組a；時(shí)間是復(fù)雜的兩個(gè)for循環(huán)。第一個(gè)循環(huán)要做一次，第二個(gè)循環(huán)要做1000次，第一個(gè)循環(huán)要做1000次，一共1000×1000次

如果兩個(gè)循環(huán)分別對(duì)應(yīng)m和N次，那么要做的次數(shù)就是m*N

你能聽懂前兩句話嗎？