2-算法效率分析基礎(chǔ)(編輯修改稿)
2025-02-08 06:59 本頁面
【文章內(nèi)容簡介】 t n) { Type key。 // cost times for (int i = 1。 i n。 i++){ // c1 n key=a[i]。 // c2 n1 int j=i1。 // c3 n1 while( j=0 a[j]key ){ // c4 sum of ti a[j+1]=a[j]。 // c5 sum of (ti1) j。 // c6 sum of (ti1) } a[j+1]=key。 // c7 n1 } } 非遞歸算法的復(fù)雜性分析 20 )1()1()1()1()1()( 7116115114321 ???????????? ?????????nctctctT niiniinii? 在最好情況下， ti=1, for 1 ? i n。 ? 在最壞情況下， ti ? i+1, for 1 ? i n。 )1()1()1()1()( 74321m in ????????? nT )()()( 743274321 nOcccccccc ????????????? ????11 12 )1()1(ni nni?????11 2)1(ninni )()(22)1(2)1(2)1(12)1()1()1()(27432765432126547654321m axnOccccccccccccncnncnncnncnT????????????????????????????? ???????? ????????????????遞歸算法的復(fù)雜性分析 21 ( 1) =1()( 1) + ( ) 1OnTnaT n f n n????T(n)=an1 T(1)+ 2()n niia f i??（ 1）若取 a=2， f(n)=O(1)，漢諾塔問題 T(n)=O(2n1) （ 2）若取 a=1， f(n)=n1，插入排序最壞情況 T(n)= O(n2) 遞歸算法的復(fù)雜性分析 22 ( 1) =1()( ) + ( ) 1OnTn naT f n nb??? ???T(n)= l o g 1l o g0( 1) ( )bbna jjjnn T a fb?? ?（ 1）若 ， ε0， （ 2） 若 ， （ 3）若 ， ε0， l o g ( ) = ( )b af n O n ?l o g( ) = ( )b aT n n? l o g( ) ( l og )b an n n??l o g( ) = ( )b af n n? l o g +( ) = ( )b af n n ??( ) ( ( ) )T n f n??遞歸算法的復(fù)雜性分析 ? 當(dāng) f(n)為常數(shù)時 ? 當(dāng) f(n) = 時 23 ??????1)(lo g1)()( l
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1