成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

歸并排序 - Algorithms, Part I, week 3 MERGESORTS

Jokcy / 3611人閱讀

摘要:兩個(gè)單元素?cái)?shù)組的合并實(shí)際就是對(duì)這兩個(gè)數(shù)進(jìn)行了排序,即變?yōu)?,同樣再?duì)后一組的兩個(gè)數(shù)歸并排序,即變?yōu)?,再將兩單元?shù)組歸并成四單元數(shù)組即和歸并為。

前言

本周講解兩個(gè)50多年前發(fā)明,但今天仍然很重要的經(jīng)典算法 (歸并排序和快速排序) 之一 -- 歸并排序,幾乎每個(gè)軟件系統(tǒng)中都可以找到其中一個(gè)或兩個(gè)的實(shí)現(xiàn),并研究這些經(jīng)典方法的新變革。我們的涉及范圍從數(shù)學(xué)模型中解釋為什么這些方法有效到使這些算法適應(yīng)現(xiàn)代系統(tǒng)的實(shí)際應(yīng)用的細(xì)節(jié)。

Mergesort。我們研究 mergesort 算法,并證明它保證對(duì) n 項(xiàng)的任何數(shù)組進(jìn)行排序,最多只能進(jìn)行 nlgn 次的比較。我們還考慮一個(gè)非遞歸的自下而上版本。我們證明,在最壞的情況下,任何基于比較的排序算法必須至少進(jìn)行 ~nlgn 的比較。我們討論對(duì)我們正在排序的對(duì)象使用不同的排序以及相關(guān)的穩(wěn)定性概念。

上一篇:基本數(shù)據(jù)類型
下一篇:快速排序

這章我們討論歸并排序,這是計(jì)算基礎(chǔ)中的兩個(gè)重要排序算法之一
我們已經(jīng)對(duì)一些算法有了科學(xué)全面的認(rèn)知,這些算法被大量運(yùn)用在系統(tǒng)排序和應(yīng)用內(nèi)排序超過50多年,我們之后所要看到的快速排序更是被在科學(xué)和工程中被譽(yù)為20世紀(jì)10大算法之一

歸并排序 概貌

所以歸并排序到底是什么樣的?

基本計(jì)劃流程:

將陣列分成兩半

遞歸排序每一半

合并兩半

它的思想其實(shí)很簡(jiǎn)單, 只要把數(shù)組一分為二, 然后再不斷將小數(shù)組遞歸地一分為二下去, 經(jīng)過一些排序再將它們合并起來, 這就是歸并排序的大致思想, 這是人們?cè)谟?jì)算機(jī)上實(shí)現(xiàn)的最早的算法之一.
(EDVAC 計(jì)算機(jī)是最早的通用型計(jì)算機(jī)之一, 馮諾依曼認(rèn)為在他的 EDVAC 中需要一種排序算法, 于是他提出了歸并排序, 因此他被公認(rèn)為是歸并排序之父)

歸并排序的核心就是“并”。所以要理解如何歸并,先考慮一種抽象的“原位歸并”。

原位歸并

也叫 Top-down mergesort. 下邊還有歸并的另一種實(shí)現(xiàn),叫 Bottom-up mergesort.

目標(biāo) 給定一個(gè)數(shù)組,它的前一半(a[lo]-[mid]) 和 后一半([mid + 1]-[hi]) 已是排好序的,我們所要做的就是將這兩個(gè)子數(shù)組合并成一個(gè)大的排好序的數(shù)組

看一個(gè)抽象原位歸并演示

1.在排序之前我們需要一個(gè)輔助數(shù)組,用于記錄數(shù)據(jù),這是實(shí)現(xiàn)歸并的最簡(jiǎn)單的方式

2.首先將原數(shù)組中所有東西拷貝進(jìn)輔助數(shù)組,之后我們就要以排好的順序?qū)⑺鼈兛截惢卦瓟?shù)組
這時(shí)我們需要三個(gè)下標(biāo):i 用于指向左邊子數(shù)組;j 指向右邊子數(shù)組;k指向原數(shù)組即排好序的數(shù)組。

3.首先取 i 和 j 所指數(shù)字中取其中小的放入原數(shù)組k的位置,當(dāng)一個(gè)被拿走之后,拿走位置的指針 (這次是 j) 和 k 遞增

4.同樣取 i 和 j 中小的那個(gè)移向 k 的位置,再同時(shí)增加移動(dòng)位置的指針(這次還是 j 和 k)

以此類推。完整演示地址:在此
這就是一種歸并方式: 用了一個(gè)輔助數(shù)組,將它們移出來又排好序放回去。
這就是歸并部分的代碼,完全依著之前的演示

Java 實(shí)現(xiàn)
public class Merge {

    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
/**
 * assertion功能: 方便我們找出漏洞并且確定算法的正確
 * 想確定a[lo] 到 a[mid] 和 a[mid+1] 到 a[hi] 是否已是排好序的
 */
        assert isSorted(a, lo, mid);
        assert isSorted(a, mid + 1, hi);

        //拷貝所有東西進(jìn)輔助數(shù)組
        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];
        /**
         * 完成歸并
         * 初始化 i 在左半邊的最左端
         * j 在右半邊最左端
         * 指針 k 從 lo 開始
         * 比較輔助數(shù)組中 i 和 j 誰(shuí)更小,并將小的那個(gè)的值移向 k
         **/
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            //如果 i 走到邊界了,就只將 j 的值都移上去
            if (i > mid) a[k] = aux[j++];
            //如果 j 走到邊界了,就只將 i 的值都移上去
            else if (j > hi) a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
        //最后再檢查最終合并后的時(shí)候排好序
        assert isSorted(a, lo, hi);
    }

    // 遞歸的 sort 方法
    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    // 對(duì)外提供接口中 sort 函數(shù)
    public static void sort(Comparable[] a) {
        //創(chuàng)建輔助數(shù)組
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length - 1);
    }
}

完整“原位”歸并代碼:在此

在這個(gè)簡(jiǎn)單的實(shí)現(xiàn)中傳入了 Comparable 類型的原數(shù)組 a[] 和 輔助數(shù)組 aux[], 還有三個(gè)參數(shù) lo, mid, and hi.
lo指向的是兩個(gè)將要合并的子數(shù)組的頭部 mid指向前一個(gè)子數(shù)組的末端 所以我們的前提是lo到mid時(shí)排好的 從mid+1到hi也是排好的

有了歸并,排序中遞歸的就簡(jiǎn)單多了。
sort() 在遞歸調(diào)用前先檢查下標(biāo),然后像二分查找那樣計(jì)算中點(diǎn)值。sort前半部分,再sort后半部分,然后merge
對(duì)外提供接口中 sort 函數(shù)只接收一個(gè)參數(shù),創(chuàng)建輔助數(shù)組的任務(wù)就交給這個(gè) sort()

這里關(guān)鍵在于不要將輔助數(shù)組在遞歸的 sort() 中創(chuàng)建, 因?yàn)槟菚?huì)多出許多額外的小數(shù)組的花費(fèi), 如果一個(gè)歸并排序效率很低通常都是由這引起 這是一個(gè)很直接的實(shí)現(xiàn)方式。也是依據(jù)了我們看到多次的一個(gè)思想--分治法:即解決問題時(shí)將其一分為二,分別解決兩個(gè)小問題,再將它們合并起來

Assertion

一般來說Java程序員,認(rèn)為加入這些 assert 是有益的:

幫助我們發(fā)現(xiàn)漏洞

同時(shí)也提示了之間的代碼的功能

這個(gè)歸并代碼就是很好的例子,如此以代碼的形式加入 assert 語(yǔ)句表明了接下來你想做什么,在代碼最后加上 assert 語(yǔ)句表明了你做了什么。
你不僅確定了代碼的正確,也告訴閱讀代碼的人你所干的事情。

Java 中 asset 語(yǔ)句接受一個(gè) boolean 值。isSorted 函數(shù)前面已經(jīng)寫過了(請(qǐng)回復(fù) -- 基本排序),如果排好序返回 true,反之返回 false. assert 在驗(yàn)證到?jīng)]正確排序時(shí)會(huì)拋出異常.

assert 可以在運(yùn)行時(shí)禁用.
這很有用因?yàn)槟憧梢园?asset 語(yǔ)句一直放在代碼中, 編程時(shí)供自己所需, 禁用后在最終上線程序中不會(huì)有額外代碼。因此 assertion 默認(rèn)是禁用的。出錯(cuò)的時(shí)候人們還可以啟用assertion然后找到錯(cuò)誤所在。

java -ea MyProgram //啟用 assertions
java -da MyProgram //禁用 assertions(默認(rèn))

所以平時(shí)最好像之前的例子那樣加入assert語(yǔ)句,并且不讓他們出現(xiàn)在產(chǎn)品代碼中,而且不要用額外的參數(shù)來做檢查。

軌跡圖

這幅圖顯示了每次調(diào)用 merge 時(shí)的操作。
我們將一個(gè)大的問題對(duì)半分,再將其中的一半對(duì)半分,對(duì)于那些分到不能再分單個(gè)元素,我們做的就是兩兩間的比較。
兩個(gè)單元素?cái)?shù)組的合并實(shí)際就是對(duì)這兩個(gè)數(shù)進(jìn)行了排序,即 M-E 變?yōu)?E-M,同樣再對(duì)后一組的兩個(gè)數(shù)歸并排序,即 R-G 變?yōu)?G-R,再將兩單元數(shù)組歸并成四單元數(shù)組,即 E-M 和 G-R 歸并為 E-G-M-R。
同樣再對(duì)后兩對(duì)歸并(E-S,O-R),這樣就得到兩個(gè)四單元數(shù)組(E-G-M-R 和 E-O-R-S), 再歸并得到八單元組(E-E-G-M-O-R-R-S).
右邊的一半也是同理,最終兩個(gè)八單元合并,得到最終的結(jié)果.
觀察這個(gè)軌跡圖對(duì)于學(xué)習(xí)遞歸算法是很有幫助的.

Q. 以下哪種子數(shù)組長(zhǎng)度會(huì)在對(duì)長(zhǎng)度為 12 的數(shù)組進(jìn)行歸并排序時(shí)出現(xiàn)?
A. { 1, 2, 3, 4, 6, 8, 12 }
B. { 1, 2, 3, 6, 12 }
C. { 1, 2, 4, 8, 12 }
D. { 1, 3, 6, 9, 12 }

算法分析 實(shí)證分析

運(yùn)行時(shí)間估計(jì):

可以將歸并排序用在大量數(shù)據(jù)中,這是個(gè)非常高效的算法。如表中所示,如果要對(duì)大量數(shù)據(jù)進(jìn)行插入排序,假設(shè)有十億個(gè)元素,用家里的電腦要花幾個(gè)世紀(jì)。就算目前的超級(jí)計(jì)算機(jī)也要花費(fèi)一個(gè)星期或更多。
但是擁有一個(gè)高效的算法,你對(duì)十億個(gè)元素排序,家用電腦也只需半小時(shí),超級(jí)計(jì)算機(jī)更是一瞬間即可完成,一些小型的問題PC也可迅速完成。因此要么你有很多錢和時(shí)間,要么你要有一個(gè)好的算法。這是我們?cè)谶@門課中的核心主題,即一個(gè)好的算法遠(yuǎn)比差的算法所花時(shí)間和金錢高效得多。

效率分析

這些數(shù)學(xué)的東西才能展示出分治法的強(qiáng)大 展示出歸并算法如何在 nlogn 時(shí)間中解決了選擇排序和插入排序需要 N^2 時(shí)間才能解決的問題。

比較次數(shù)

命題:對(duì)于大小為 n 的數(shù)組,歸并排序需要最多 nlogn 次比較 和 6nlogn 次數(shù)組訪問

證明:證明這個(gè)結(jié)論就是需要從之前的代碼中得出遞推關(guān)系式, 這便是代碼所反映的數(shù)學(xué)問題。
如果對(duì) n 個(gè)元素排序,用關(guān)于 n 的函數(shù) C(n) 來表示需要比較的次數(shù)

歸并時(shí)左半部分和右半部分元素個(gè)數(shù)就用 n/2 上取整 和 n/2 下取整來表示, 這就是兩個(gè)子數(shù)組的大小. 因?yàn)槲覀冞f歸地調(diào)用函數(shù), 所以括號(hào)里就是每次遞歸時(shí)分割后子數(shù)組的大小, 于是整個(gè)一項(xiàng)就是子數(shù)組中這些數(shù)排序需要的比較次數(shù).
對(duì)于左半部分比較次數(shù), 就是關(guān)于 n/2 上取整的函數(shù) C(n/2); 對(duì)于右邊同理. 二合并時(shí)我們需要至多 n-1 次比較
因?yàn)槿绻笥覜]有一邊提前排完,就需要 n-1 次比較. 這也只是 n 大于等于 1 的情況. 如果只有一個(gè)單元, 是不需要任何比較的, C(1) = 0.
于是這個(gè)從代碼中考查得來的公式就能精確計(jì)算所需要的比較次數(shù)上界.

關(guān)于這些求這些復(fù)雜公式的通項(xiàng),具體可以回顧離散數(shù)學(xué)

我們可以看一下當(dāng) n 為 2 的冪時(shí)的情況(但結(jié)論是對(duì) n 為任意數(shù)都成立的, 我們可以通過數(shù)學(xué)歸納法來證明)

D(n) = 2 D(n / 2) + n, for n > 1, with D(1) = 0. 

和前面相似的遞推關(guān)系式, 我們將展示一種證明方法.

分治遞歸
都假設(shè) n 為 2 的冪次,那 n^2 除以二也是 2 的冪, 這是顯然的。
命題: 當(dāng) n 是 2 的冪次時(shí)的情況, 即,如果 D(n) 滿足 D(n) = 2 D(n / 2) + n,當(dāng) n > 1, 當(dāng)且僅當(dāng) n=1 時(shí) D(1)=0,通項(xiàng) D(n) = nlogn.

圖示法

!

可以看到每次歸并,對(duì)于一整層的比較次數(shù)都是 N 次,所以共有多少層? 將 N 不斷除 2 一直到等于2,一共有 logN 層(以2為底), 所以總共有 NlogN 次比較。歸并的全部開銷就在于比較次數(shù), 也就是 NlogN. 這就是用圖示法來計(jì)算遞推式.

數(shù)組訪問

命題:對(duì)于大小為 n 的數(shù)組,歸并排序使用 ≤ 6nlgn 個(gè)數(shù)組訪問來排序數(shù)組

對(duì)于數(shù)組訪問次數(shù)的計(jì)算相似, 只是在歸并的時(shí)候后面加上的是 6n

將 a 數(shù)組復(fù)制到 aux 數(shù)組:數(shù)組訪問 2 n 次; 如果 less() 方法運(yùn)行了 2 n 次,如果每次 less() 都返回 true, 那么又需要 2 * n 次來將輔助數(shù)組中的值儲(chǔ)存回原數(shù)組,所以總共 6n 次

A(n) ≤ A(?n / 2?) + A(?n / 2?) + 6n for n > 1, with A(1) = 0. 

Key point. 任何具有以下結(jié)構(gòu)的算法都需要 nlogn 時(shí)間

內(nèi)存占用

命題: Mergesort 使用與 n 成比例的額外空間
歸并排序的一大特點(diǎn)就是它需要隨 n 增大而增大的額外空間, 因?yàn)橛心莻€(gè)額外的輔助數(shù)組.

證明: 對(duì)于最后一次合并,數(shù)組aux []的長(zhǎng)度必須為n。
我們將兩個(gè)子數(shù)組看似原地排序, 但實(shí)際上并不是真正的“原地”, 因?yàn)槲覀冇玫搅祟~外的數(shù)組。

如果使用 ≤ clogn 的額外內(nèi)存,則排序算法就是原地排序,例如:
插入排序,選擇排序,和 希爾排序

這些排序算法不需要額外空間,但歸并排序你只能放一半,另一半要留給輔助數(shù)組。

算法改進(jìn)

如果你覺得現(xiàn)在所學(xué)的太簡(jiǎn)單,而在思考一種真正的原地歸,其實(shí)人們已經(jīng)有一些方法來完成,但只是理論上可行,實(shí)踐太過繁瑣,而沒有能被運(yùn)用,也許存有簡(jiǎn)單的方式實(shí)現(xiàn)原地歸并,這就有待我們?nèi)グl(fā)現(xiàn)。
不過現(xiàn)在有些切實(shí)可行的改進(jìn),能讓歸并算法變得高效,這就來看一下因?yàn)檫@種技巧也能用于其他算法:

使用數(shù)組長(zhǎng)度為 ~ ? n 的額外數(shù)組 aux[] 代替長(zhǎng)度為 n 的額外數(shù)組
首先對(duì)特別小的數(shù)組運(yùn)用歸并排序太過復(fù)雜,比如大小為二三四的數(shù)組,歸并它們時(shí)調(diào)用函數(shù)也會(huì)有開銷,更糟糕的是不斷地遞歸會(huì)分出很多很多小數(shù)組,所以第一個(gè)改進(jìn)就是進(jìn)行切分,對(duì)小于某個(gè)數(shù)值的小數(shù)組采用插入排序,這樣能更加有效。 所以加入這一行能讓歸并更快,快大約20%。

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
 //Cutoff to insertion sort for ≈ 7 items.
 if (hi <= lo + CUTOFF - 1)
 {
     Insertion.sort(a, lo, hi);
     return;
 }
     int mid = lo + (hi - lo) / 2;
     sort (a, aux, lo, mid);
     sort (a, aux, mid+1, hi);
     merge(a, aux, lo, mid, hi);
}

第二個(gè)對(duì)算法的改進(jìn)可以是當(dāng)(merge之前)兩個(gè)子數(shù)組間如果已是有序,便可跳過此輪歸并。判斷這種情況只需判斷前一半最大的數(shù)是否小于后一半最小的數(shù),僅此而已,So easy. 因此我們就在歸并前加一句判斷,檢測(cè)子數(shù)組是否有序,這樣只要在每個(gè)歸并前檢測(cè)一下,也只需線性復(fù)雜度的時(shí)間即可完成,這至少在一些情況下是有幫助的

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
     if (hi <= lo) return;
     int mid = lo + (hi - lo) / 2;
     sort (a, aux, lo, mid);
     sort (a, aux, mid+1, hi);
     //are subarrays sorted?
     if (!less(a[mid+1], a[mid])) return;
     merge(a, aux, lo, mid, hi);
}

另一個(gè)可以改進(jìn)的比較費(fèi)解, 所以只推薦于專業(yè)人士.改進(jìn)在于節(jié)省下拷貝到輔助數(shù)組的時(shí)間(不是空間)。這種改進(jìn)相當(dāng)于每一輪遞歸時(shí)轉(zhuǎn)換一下原數(shù)組和輔助數(shù)組的角色,不過還是需那個(gè)輔助數(shù)組。代碼如下:

將sort結(jié)果放入另一數(shù)組,將merge結(jié)果合并回原數(shù)組,所以遞歸函數(shù)同時(shí)也完成了交換兩個(gè)數(shù)組角色的任務(wù),這就意味著不用花時(shí)間拷貝元素進(jìn)輔助數(shù)組,就節(jié)省下了一點(diǎn)時(shí)間。

完整代碼:在此

穩(wěn)定性

我們上訴實(shí)現(xiàn)的歸并排序是穩(wěn)定的嗎?是穩(wěn)定的。
穩(wěn)定性又是指什么。請(qǐng)查看前一章:基本排序

歸并排序是穩(wěn)定的,只要 merge() 操作是穩(wěn)定的,它就是穩(wěn)定的。

public class Merge
{
 private static void merge(...)
 { /* as before */ }

 private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
 {
     if (hi <= lo) return;
     int mid = lo + (hi - lo) / 2;
     sort(a, aux, lo, mid);
     sort(a, aux, mid+1, hi);
     //這個(gè)操作是穩(wěn)定的
     merge(a, aux, lo, mid, hi);
 }
 public static void sort(Comparable[] a)
 { /* as before */ }
}

這些操作是否穩(wěn)定取決于我們的代碼怎么寫。在我們的代碼中,

private static void merge(...)
{
 for (int k = lo; k <= hi; k++)
 aux[k] = a[k];
 int i = lo, j = mid+1;
 for (int k = lo; k <= hi; k++)
 {
     if (i > mid) a[k] = aux[j++];
     else if (j > hi) a[k] = aux[i++];
     else if (less(aux[j], aux[i])) a[k] = aux[j++];
     // 如果兩個(gè)鍵是相等(或左邊子數(shù)組的值小),將輔助數(shù)組左邊的值放到原數(shù)組中
     else a[k] = aux[i++];
 }
} 

如果兩個(gè)鍵是相等的,它取來自左邊子數(shù)組的值,那么這意味著如果有兩組相等的鍵,它將總是保留它們的相對(duì)順序,先左再右,這就足夠表示歸并操作是穩(wěn)定的了,因此歸并排序是穩(wěn)定的。穩(wěn)定性是排序算法中一個(gè)重要的性質(zhì)。歸并算法不僅高效而且也是穩(wěn)定的。

bottom-up 歸并排序

這是一種簡(jiǎn)單,沒有遞歸的,歸并排序的實(shí)現(xiàn)方法

歸并規(guī)則

接下來,我們將看從下往上方式的歸并排序。
歸并排序作為遞歸程序是簡(jiǎn)單易理解的。雖然這個(gè)從下往上的方式不是遞歸,但也比較容易理解。
其基本方法為:

把開始未排序的每一個(gè)元素視為已排序的序列,該序列長(zhǎng)度為 1

接下來此方法將遍歷并合并 1 對(duì)長(zhǎng)度為 1 的子序列,成為一組長(zhǎng)度為二的子序列

然后對(duì)長(zhǎng)度為 2 的子序列進(jìn)行合并再排序,這樣我們就有一組長(zhǎng)度為 4 的已排序的子序列

然后合并長(zhǎng)度為 8 以此類推

從這個(gè)例子中我們可以看出,從長(zhǎng)度為 1 的子序列開始,合并排序成長(zhǎng)度為 2 的子序列 E-M,然后不斷重復(fù)這一過程,直到我們從 16 個(gè)長(zhǎng)度為 1 的子序列變?yōu)閮山M長(zhǎng)度為八的子序列

在第二輪中,我們將 E-M 與另一組 G-R 合并排序?yàn)镋-G-M-R,以及 E-S 與 O-R 合并為 E-O-R-S,以此類推,我們有四組長(zhǎng)度為四的子序列

第三輪我們將每?jī)山M合并,得到兩組長(zhǎng)度為八的子序列,最后一輪的到一個(gè)完全排序的序列。

這樣做的好處是這一操作遍歷整個(gè)序列并且不需要遞歸。

Java 實(shí)現(xiàn)
public class MergeBU
{
 private static void merge(...)
 { /* as before */ }

 public static void sort(Comparable[] a)
 {
     int n = a.length;
     Comparable[] aux = new Comparable[n];
     for (int sz = 1; sz < n; sz = sz+sz)
         for (int lo = 0; lo < n-sz; lo += sz+sz)
             merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, n-1));
     }
}

完整代碼:在此

從以上代碼可以看出它非常容易編寫,

采用同樣的合并代碼并運(yùn)用嵌套循環(huán)(兩個(gè) for 循環(huán)),sz 子序列的大小,第一層循環(huán)是 logn 時(shí)間復(fù)雜度,因?yàn)槊看挝覀兒喜⑿蛄袨閮杀堕L(zhǎng),即 sz = sz+sz,直到長(zhǎng)度為 n。

然后我們從 low 到 low+size-1 排序

這就是一個(gè)完全達(dá)到業(yè)界標(biāo)準(zhǔn)的排序代碼,相對(duì)普通歸并排序,它的唯一負(fù)面影響在于需要額外存儲(chǔ)空間,大小與序列長(zhǎng)度有關(guān)。
除了這點(diǎn)外這是一個(gè)很好的歸并排序方法。
以上是從下往上的歸并排序。無(wú)論大小,從下往上的歸并排序 時(shí)間復(fù)雜度為 logN。而每一輪需要進(jìn)行N次比較,因此總復(fù)雜度為 NlogN

排序復(fù)雜度

學(xué)習(xí)歸并排序能很好的來幫助理解排序問題自身存在的困難性,現(xiàn)在把這個(gè)困難度稱為復(fù)雜度,接下來我們將會(huì)看關(guān)于復(fù)雜度的問題。

計(jì)算復(fù)雜性

計(jì)算復(fù)雜性: 研究解決特定問題 X 的(所有)算法效率的框架.

而為了使其易于理解,我們需要建立所謂的計(jì)算模型,即
計(jì)算模型: 算法允許執(zhí)行的操作

對(duì)于那種直截了當(dāng)?shù)呐判?,我們要做的是建立一個(gè)成本模型來計(jì)算比較次數(shù)。
成本模型: 操作計(jì)數(shù)。

現(xiàn)在,在問題復(fù)雜度的框架內(nèi)我們只有兩樣?xùn)|西:
上限: 算法所用開銷/成本的保證,它是由一些(!!)為了解決問題而設(shè)計(jì)的算法提供。這個(gè)上限就表示解決這個(gè)問題有多難,我們有個(gè)算法可以解決它,并且這是最簡(jiǎn)單的。
下限:下限,這是對(duì)所有算法的成本/開銷保證的限制。 沒有算法的下限比這個(gè)下線做得更好了。
然后我們尋求所謂的最優(yōu)的算法,就是解決問題“最優(yōu)的”算法。
最優(yōu)算法:待解問題的最佳成本保證的算法。也可以說是算法的上限和下限是幾乎相同的(upper bound ~ lower bound),這是解決任何問題的最理想目標(biāo)

因此,對(duì)于排序,讓我們看看這各部分分別是什么。
假設(shè)我們?cè)L問數(shù)據(jù)的唯一方式是通過比較操作,我們所有能使用的只有比較操作,那么一下就是用于分析排序復(fù)雜度的框架:

舉例:排序問題

計(jì)算復(fù)雜性(框架)

計(jì)算模型 model of computation:comparison tree (舊版本的講義decision tree)

comparison tree 意味著只能在進(jìn)行比較的時(shí)候訪問數(shù)組(e.g., Java Comparable framework)

成本模型 cost model:比較的次數(shù)

用 #compares 表示

上界upper bound:~ n lg n from mergesort.

歸并排序提供了一個(gè)上界,它是一個(gè)保證排序完成的時(shí)間與 nlogn 成正比的算法.

下界lower bound:?

最優(yōu)算法optimal algorithm:?

以下是證明排序下界的基本思想

比較樹

比方說,我們有3個(gè)不同的項(xiàng),a, b 和 c。不論使用什么算法我們首先要做的是比較三項(xiàng)中的兩項(xiàng)。

分解
比如說,這里是a 和 b。比較之后,有兩種情況 b < c / a < c, 也就是說,它們是有區(qū)別的, 在比較中間會(huì)有一些代碼,但不管怎樣接下來里有不同的比較。

在這種情況下,如果你從樹的頂部到尾部使用至多三次比較你就可以確定三個(gè)不同元素的順序。
用下限的觀點(diǎn)概括就是你需要找到一個(gè)最小的比較次數(shù)來確定N個(gè)元素的順序。

現(xiàn)在,樹的高度,樹的高度,正如我剛剛提到的,是最差情況下比較的次數(shù)。
在所有排序中即使是考慮最差情況下的樹,無(wú)論輸入是什么,這棵樹告訴我們一個(gè)邊界,以及算法的比較次數(shù)。

在每一個(gè)可能的順序中都至少有一個(gè)順序,如果有一個(gè)順序沒有出現(xiàn)在針對(duì)特定算法的樹中,那么這個(gè)算法就不能排序,不能告訴你兩種不同順序中間的差別。

作為命題的下界,使用比較樹來證明任何基于排序算法的比較在最差情況下不得不使用至少 log2(N) 因子的比較次數(shù)

并且,通過斯特林近似公式,我們知道 lg(N!) 與 Nlg(N) 成正比。

基于比較的排序算法下界

命題:任何基于比較的排序算法,在最壞的情況下, 必須至少做出 lg(n!)~nlgn 次比較。
證明

假設(shè)數(shù)組由 n 個(gè)不同的值 a1 到 an 組成

由比較樹的高度h決定最壞情況下排序需要比較的次數(shù)

高度為 h 的二叉樹具有 ≤2^h 的葉子

N! 個(gè)不同的順序 ? n! 個(gè)可到達(dá)的葉子

h 是最會(huì)情況下,也就是擁有最多葉子的情況下的高度

2^h大于等于葉子節(jié)點(diǎn)的數(shù)量

葉子節(jié)點(diǎn)的數(shù)量大于等于N!

這推導(dǎo)出:樹的高度大于等于log2(N!),根據(jù)斯特林公式,那是正比于 NlogN

這就是排序算法復(fù)雜度的下限。那么上限的話,根據(jù)上邊排序問題的計(jì)算復(fù)雜性(框架),已經(jīng)知道上限是 NlogN, 那意味著歸并排序就是一個(gè)最優(yōu)算法(上限 = 下線)

算法設(shè)計(jì)的首要目標(biāo):嘗試給我們要解決的問題找到最優(yōu)算法

通過復(fù)雜性分析得出的上下文結(jié)果:

我們真正證明的是:
歸并排序,就比較的次數(shù)而言,是最優(yōu)的
但是它就空間使用并非最優(yōu),歸并排序使用多一倍的額外空間,正比于它要處理的數(shù)組的大小。而簡(jiǎn)單的算法,比如插入或其他排序,他們根本不適用任何額外的空間。

所以,當(dāng)我們關(guān)注實(shí)現(xiàn)并嘗試解決實(shí)際問題時(shí),我們把這些理論結(jié)果用作一個(gè)指導(dǎo)。
在這個(gè)例子里,它告訴我們的是:
比如,不要嘗試設(shè)計(jì)一個(gè)排序算法保證大體上比歸并排序,在比較次數(shù)上,更好的算法,比方說,1/2NlogN。有方法使用 1/2NlogN次比較的嗎?下限說,沒有;
再比如,也許有一個(gè)算法,使用 NlogN 次比較,同時(shí)也有最優(yōu)的空間利用率。不僅在時(shí)間上,也在空間上都是最優(yōu)的。我們即將看到在下面談?wù)撨@樣的算法。

另一件事是,特定模型下的下限是針對(duì)正在研究的特定計(jì)算模型得出的,在這個(gè)例子中是比較的次數(shù)。如果算法有關(guān)于鍵值的更多信息,它可能不成立。如果算法可以利用以下優(yōu)勢(shì),則下限可能不成立:

輸入數(shù)組的初始順序

例如:插入排序只需要對(duì)部分排序的數(shù)組進(jìn)行線性數(shù)量的比較。又或者如果輸入是幾乎排序好的。我們?cè)吹綄?duì)于幾乎排序好的文件,插入排序可以是線性時(shí)間的。

鍵值的分布

如果有許多相等的鍵,我們可以令它排序得比 NlogN 更快。還有 3-way quicksort 快速排序僅需要在具有恒定數(shù)量的不同鍵的數(shù)組上進(jìn)行線性數(shù)量的比較。(后續(xù)章節(jié))

鍵的表示

例如:基數(shù)排序不需要鍵值的比較 - 它們直接通過訪問數(shù)據(jù). 通過字符/數(shù)位(digit)比較。后續(xù)章節(jié))
我們可以利用數(shù)字字符的比較,而不是整個(gè)鍵的比較,并對(duì)特定的實(shí)際應(yīng)用得到一個(gè)更快地排序。

計(jì)算復(fù)雜度是一個(gè)非常有用的方法來幫助我們理解算法的性質(zhì)并幫助指導(dǎo)我們的設(shè)計(jì)決策。

附錄

Q. 以下哪種子數(shù)組長(zhǎng)度會(huì)在對(duì)長(zhǎng)度為 12 的數(shù)組進(jìn)行歸并排序時(shí)出現(xiàn)?
B. { 1, 2, 3, 6, 12 }

對(duì)上下界理解的補(bǔ)充
到目前為止,我們一直關(guān)注這個(gè)問題:“給定一些問題X,我們能否構(gòu)建一個(gè)在大小為n的輸入上運(yùn)行時(shí)間O(f(n))的算法?”
這通常被稱為上限問題,因?yàn)槲覀冋诖_定問題X的固有難度的上界,我們的目標(biāo)是使f(n)盡可能小。

下界問題, 這里,目標(biāo)是證明任何算法必須花費(fèi)時(shí)間 Ω(g(n))時(shí)間來解決問題,現(xiàn)在我們的目標(biāo)讓 g(n)盡可能大。
下限幫助我們理解我們與某個(gè)問題的最佳解決方案有多接近:
例如,如果我們有一個(gè)在上界時(shí)間 O(n log^2 n) 和 下界Ω(n log n) 運(yùn)行的算法,那么我們的算法有l(wèi)og(n) 的 “差距”:我們希望通過改進(jìn)算法縮小這個(gè)差距。

通常,我們將在限制的計(jì)算模型中證明下限,指定可以對(duì)輸入執(zhí)行什么類型的操作以及執(zhí)行什么開銷。因此,這種模型的下限意味著如果我們想要算法做得更好,我們需要以某種方式在模型之外做一些事情。
今天我們考慮基于比較的排序算法類。這些排序算法僅通過比較一對(duì)鍵值對(duì)輸入數(shù)組進(jìn)行操作,在比較的基礎(chǔ)上移動(dòng)元素。

面試問題 編程練習(xí)

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://m.hztianpu.com/yun/77475.html

相關(guān)文章

  • 基本排序 - Algorithms, Part I, week 2 ELEMENTARY SORTS

    摘要:我們討論比較排序算法的理論基礎(chǔ),并結(jié)合本章應(yīng)用排序和優(yōu)先級(jí)隊(duì)列算法?;九判蛞肓诉x擇排序,插入排序和。描述了,一種保證在線性時(shí)間內(nèi)運(yùn)行的排序算法。當(dāng)我們后續(xù)實(shí)現(xiàn)排序算法時(shí),我們實(shí)際上將這個(gè)機(jī)制隱藏在我們的實(shí)現(xiàn)下面。 前言 上一篇:棧和隊(duì)列下一篇:歸并排序 排序是重新排列一系列對(duì)象以便按照某種邏輯順序排列的過程。排序在商業(yè)數(shù)據(jù)處理和現(xiàn)代科學(xué)計(jì)算中起著重要作用。在交易處理,組合優(yōu)化,天體...

    BLUE 評(píng)論0 收藏0
  • 幾種常見排序算法

    摘要:本文介紹幾種常見排序算法選擇排序,插入排序,希爾排序,歸并排序,快速排序,堆排序,對(duì)算法的思路性質(zhì)特點(diǎn)具體步驟實(shí)現(xiàn)以及圖解進(jìn)行了全面的說明。最后對(duì)幾種排序算法進(jìn)行了比較和總結(jié)。 本文介紹幾種常見排序算法(選擇排序,插入排序,希爾排序,歸并排序,快速排序,堆排序),對(duì)算法的思路、性質(zhì)、特點(diǎn)、具體步驟、java實(shí)現(xiàn)以及trace圖解進(jìn)行了全面的說明。最后對(duì)幾種排序算法進(jìn)行了比較和總結(jié)。 寫...

    ChristmasBoy 評(píng)論0 收藏0
  • 算法分析 - Algorithms, Part I, week 1 ANALYSIS OF ALGO

    摘要:實(shí)際上這個(gè)情形中存在冪定律實(shí)際上絕大多數(shù)的計(jì)算機(jī)算法的運(yùn)行時(shí)間滿足冪定律?;谘芯康弥?,原則上我們能夠獲得算法,程序或者操作的性能的精確數(shù)學(xué)模型。 前言 上一篇:并查集下一篇:棧和隊(duì)列 在算法性能上我們常常面臨的挑戰(zhàn)是我們的程序能否求解實(shí)際中的大型輸入:--為什么程序運(yùn)行的慢?--為什么程序耗盡了內(nèi)存? 沒有理解算法的性能特征會(huì)導(dǎo)致客戶端的性能很差,為了避免這種情況的出線,需要具備算法...

    Leo_chen 評(píng)論0 收藏0
  • JavaScript 排序算法圖解(JavaScript sorting algorithms

    摘要:基礎(chǔ)構(gòu)造函數(shù)以下幾種排序算法做為方法放在構(gòu)造函數(shù)里。代碼圖解選擇排序選擇排序算法是一種原址比較排序算法。它的性能通常比其他的復(fù)雜度為的排序算法要好。代碼劃分過程圖解排序沒有定義用哪個(gè)排序算法,所以瀏覽器廠商可以自行去實(shí)現(xiàn)算法。 基礎(chǔ)構(gòu)造函數(shù) 以下幾種排序算法做為方法放在構(gòu)造函數(shù)里。 function ArrayList () { var array = []; // 交換位置...

    h9911 評(píng)論0 收藏0
  • java-工具類Collections和Arrays的設(shè)計(jì)和區(qū)別

    摘要:排序的算法是歸并排序。舉個(gè)例子,的算法可以不是使用歸并排序,但是該算法一定要是穩(wěn)定的。這個(gè)類是的一部分。官方這個(gè)類只包含操作或返回集合的靜態(tài)方法。具體來說是,第一步,先把集合轉(zhuǎn)換為數(shù)組,第二步,調(diào)用。和沒有什么區(qū)別,只是傳參有點(diǎn)不同。 Arrays 1.作用看類的名字,就知道是對(duì)數(shù)組(數(shù)據(jù)類型[])進(jìn)行各種操作。例如,排序、查找、復(fù)制等。 排序的算法是歸并排序。查找的算法是二分查找。復(fù)...

    mj 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<