《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）（第2版）》教學(xué)課件1-04算法的時(shí)間和空間復(fù)雜度

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：簡(jiǎn)勇算法的時(shí)間和空間復(fù)雜度常州信息職業(yè)技術(shù)學(xué)院02三、鏈表的插入03算法的時(shí)間和空間復(fù)雜度0.4一、算法的時(shí)間復(fù)雜度12設(shè)問(wèn)題的規(guī)模為n，把一個(gè)算法的時(shí)間耗費(fèi)T(n)稱為該算法的時(shí)間復(fù)雜度，它是問(wèn)題規(guī)模為n的函數(shù)。（1）定義：（2）算法的漸進(jìn)時(shí)間復(fù)雜度設(shè)T(n)為一個(gè)算法的時(shí)間復(fù)雜度，如果存在一個(gè)函數(shù)f(n)，當(dāng)n趨向無(wú)窮大時(shí)T(n)與函數(shù)f(n)比值的極限是一個(gè)非零常數(shù)M，即 ，則稱O(f(n)為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度，也稱T(n)與f(n)的數(shù)量級(jí)相同，記作T(n)=O(f(n)，通常，f(n)應(yīng)該是算法中頻度最高的語(yǔ)句的頻度

2、。因此，計(jì)算算法的時(shí)間復(fù)雜度只需計(jì)算算法中執(zhí)行頻度最高的語(yǔ)句的頻度。04算法的時(shí)間和空間復(fù)雜度0.4一、算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度有很多，常用的時(shí)間復(fù)雜度及順序如下：O(1)O(lgn)O(n)O(nlgn)O(n2)O(n3)=0&(Ai!=K)(3)i-;(4)return i;此算法中第(3)行語(yǔ)句的頻度最高，它不僅與問(wèn)題規(guī)模n有關(guān)，還與輸入實(shí)例中數(shù)組A各元素的取值及K的取值有關(guān)：若A中沒有與K相等的元素，則語(yǔ)句i-;的頻度f(wàn)(n)=n；若A的最后一個(gè)元素等于K，則語(yǔ)句i-;的頻度f(wàn)(n)是常數(shù)0。34（3）常用算法時(shí)間復(fù)雜度的順序（4）算法的時(shí)間復(fù)雜度不僅僅依賴于問(wèn)題的規(guī)模，還與

3、輸入實(shí)例的初始狀態(tài)有關(guān)。05算法的時(shí)間和空間復(fù)雜度0.4一、算法的時(shí)間復(fù)雜度（5）最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度最壞情況下的時(shí)間復(fù)雜度稱為最壞時(shí)間復(fù)雜度。最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的上界。平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下，算法的期望運(yùn)行時(shí)間。如果不作特別說(shuō)明，我們討論的時(shí)間復(fù)雜度均是平均時(shí)間復(fù)雜度?！纠?-1】求在含有n（n3）個(gè)元素的數(shù)組array中輸出第3個(gè)元素的算法時(shí)間復(fù)雜度。(1) i=3;(2) printf(%dn,arrayi);【例1-2】求下列算法的時(shí)間復(fù)雜度。(1) x=1;(2) for(i=1;i=n;i+)(3) for(j=1;j=i;j+)(4) for(k=1;k=j;k+)(5)x+;06算法的時(shí)間和空間復(fù)雜度0.4二、算法的空間復(fù)雜度空間復(fù)雜度(Space complexity) ：是指算法編寫成程序后，在計(jì)算機(jī)中運(yùn)行時(shí)所需存儲(chǔ)空間大小的度量。記作： S(n)=O(f(n) 其中： n為問(wèn)題的規(guī)模(或大小)該存儲(chǔ)空間一般包括三個(gè)方面： 指令常數(shù)變量所占用的存儲(chǔ)空間; 輸入數(shù)據(jù)所占用的存儲(chǔ)空間; 輔助(存儲(chǔ))空間。 一般地，算法的空間復(fù)雜度指的是輔助