• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            ArcTan

            dfs
            隨筆 - 16, 文章 - 117, 評論 - 6, 引用 - 0
            數據加載中……

            Stooge排序

              《算法導論》7-3看到了這個好東東,beautiful-sort,代碼確實漂亮。不愧是教授啊,Howard,Fine,膜拜ing.
            int stooge_sort(int a[],int s,int t)
            {
                
            int k;
                
            if (a[s]>a[t])
                    swap(a[s],a[t],k);
                
            if (s+1>=t)
                    
            return 0;
                k
            =(t-s+1)/3;
                stooge_sort(a,s,t
            -k);
                stooge_sort(a,s
            +k,t);
                stooge_sort(a,s,t
            -k);
            }

            a) 證明:如果n=Length[A],那么STOOGE-SORT(A, 1, Length[A])能正確地對輸入數組A[1..n]進行排序。

            循環不變式:過程STOOGE-SORT(A, i, j)被調用后,數組A中[i, j]區間內的元素是有序的。
            初始化:i+1>=j時,[i, j]區間中只有一個或者兩個元素,唯一的操作就是 if A[i]>A[j] then exchange A[i]<->A[j],顯然循環不變式是成立的。
            保 持:每一次STOOGE-SORT(A, i, j)被調用時,假設循環不變式成立。則調用STOOG-SORT(A, i, j-k)使得區間[i, j-k]有序,調用STOOG-SORT(A, i+k, j)使得區間[i+k, j]有序。因為k=(j-i+1)/3,所以區間[i, j-k]和區間[i+k, j]的重疊部分區間[i+k, j-k]的元素個數為[i, j]中元素個數的1/3,也為k個。因調用STOOG-SORT(A, i, j-k)后區間[i, j-k]有序,所以區間[i+k, j-k]中的元素應該是區間[i, j-k]中最大的k個元素,于是調用STOOG-SORT(A, i+k, j)后可以保證區間[j-k+1, j]中包含區間[i, j]中最大的k個元素并且是有序的。因此可保證在第二次調用STOOG-SORT(A, i, j-k)后區間[i, j]有序。
            終止:STOOGE-SORT(A, i, Length[A])調用結束后,根據循環不變式,數組A中的元素是有序的。

            b) 給出一個表達STOOGE-SORT最壞情況的運行時間的遞歸式,以及關于最壞情況運行時間的一個緊確的漸進(Θ記號)界。

            T(n)=3T(2n/3)+Θ(1)

            根據主定理:

            a=3    b=3/2    f(n)=Θ(1)

            故有 f(n)=O(n^log(3/2, 3-ε))  (ε>0)

            所以 T(n)=Θ(n^log(3/2, 3))>Θ(n^2)


            復制了大牛的文章過來,沒事自己看看。

            不過怎么覺得Thomas.H.Cormen等人有點諷刺諷刺這幾個教授呢??

            posted on 2012-03-21 11:05 wangs 閱讀(523) 評論(0)  編輯 收藏 引用 所屬分類: ACM-201203

            久久久久人妻一区精品色 | 一级做a爱片久久毛片| 日韩精品久久无码人妻中文字幕| 国产精品久久久久久久久久影院| 亚洲伊人久久大香线蕉综合图片 | 精品久久人人爽天天玩人人妻| 国产精品成人久久久久三级午夜电影 | 99久久中文字幕| 久久久久久午夜精品| 国产午夜精品理论片久久影视| 久久久免费观成人影院 | 少妇人妻综合久久中文字幕| 久久人人爽人人爽人人片AV不| 99久久国产综合精品成人影院| 精品综合久久久久久98| 伊人久久综在合线亚洲2019 | 欧美亚洲国产精品久久| 99久久亚洲综合精品成人| 无遮挡粉嫩小泬久久久久久久| 久久久久成人精品无码 | 老司机午夜网站国内精品久久久久久久久 | 久久综合欧美成人| 亚洲午夜久久久影院| 久久久WWW成人免费精品| …久久精品99久久香蕉国产| 精品久久久久久中文字幕大豆网| 久久99久久成人免费播放| 久久婷婷综合中文字幕| 久久精品国产网红主播| 亚洲中文字幕无码久久综合网| 亚洲国产精品狼友中文久久久| 99久久精品免费| 青青草原综合久久| 国产福利电影一区二区三区,免费久久久久久久精 | 久久精品国产一区二区三区不卡| 国内精品久久久久久99蜜桃| 久久无码高潮喷水| 亚洲va久久久噜噜噜久久狠狠 | 婷婷国产天堂久久综合五月| 蜜臀久久99精品久久久久久| 亚洲欧美日韩精品久久亚洲区|