国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

DS&ALGR : 通過簡單排序理解大O表示法

Eirunye / 2746人閱讀

摘要:在上面的三種排序中,它們的效率為用大表示法來表示都是,但實際上按比較的次數和交換的次數來考慮,插入排序效率高于選擇排序,選擇排序效率高于冒泡排序。大表示法常見的基于的走勢圖如下圖所示

大O表示法初體驗
身在斯洛文尼亞的阿拉里克得到斯提里科被殺的消息后,仰天大笑:“終于沒有人能阻止我去羅馬了。”
當他手下的將軍問:“不知大王打算走哪條路去羅馬?”
西哥特王哈哈大笑,說出了那句千古名言:All roads lead to Rome


條條大路通羅馬,這句著名的英語諺語告訴人們,達到同一目的可以有多種不同的方法和途徑
在編程中同樣如此,同樣一個編程問題,十個程序員可能會寫出十種程序,算法各不相同,確實是條條大路通羅馬。
但程序員對算法的效率可不會像西哥特王那般豪放和豁達,程序員對于算法的效率十分在乎,盡管算法無論效率高低,均能解決問題,但效率高的算法,除了能解決問題,還可以在問題規模變大變復雜時,高效地解決問題。

于是,我們面臨一個問題,那就是如何評價,以及從什么角度去評價一個算法。

通常,我們可能說,這個算法比那個算法更快一點,但這個比較是沒有意義的。當算法要處理的數據項數量不同時,誰快誰慢都要重新評價。

評價算法時,應該結合數據量來評價,即當數據量增大時,算法所消耗的時間變化趨勢。

在計算機世界中,這種粗略的評價方式被稱為大O表示法

簡單排序 冒泡排序

冒泡排序先從數組最左邊開始,比較第1個和第2個元素的值,值比較高的往數組的高位排,然后依次比較第2和第3個元素,值比較大的往高位排,一直比較到倒數第2個和倒數第1個元素,這稱為第一趟排序,這一趟就能確定數組中值最大的那個元素,并把這個最大的元素排到數組的最高位。
依次類推,第二趟排序會確定數組中第二大的元素,并把它排在最大的元素前邊。
假設數組有n個元素,那么經過n-1趟排序,數組的元素就是有序的。
因為每一趟中,最大的元素就像水泡一樣,冒到了數組的高位,冒泡排序因此得名。

/**
 *
 *
 * @author beanlam
 * @date 2016年3月9日 下午11:26:20
 * @version 1.0
 *
 */
public class SimpleSort {

    public static void bubbleSort(final int[] array) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException("array");
        }
        
        int length = array.length;
        for (int outLoop = length - 1; outLoop > 0; outLoop-- ) {
            for (int innerLoop = 0; innerLoop < outLoop; innerLoop++) {
                if (array[innerLoop] > array[innerLoop + 1]) {
                    swap(array, innerLoop, innerLoop + 1);
                }
            }
        }
    }
    
    private static void swap(final int[] array, final int left, final int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}
選擇排序

選擇排序的過程是從左向右掃描數組,并從中找出最小值的元素,把它放在左邊已知的最小位置上,比如第一趟掃描,找出最小的元素后,將該元素放到數組的下標0處。第二趟掃描從下標1開始掃描,找出最小元素后,放到下標1處。總共需要掃描n-1次,就能使該數組處于有序狀態。

/**
 *
 *
 * @author beanlam
 * @date 2016年3月9日 下午11:26:20
 * @version 1.0
 *
 */
public class SimpleSort {

    public static void selectionSort(final int[] array) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException("array");
        }
        
        int length = array.length;
        int minIndex;
        for (int outLoop = 0; outLoop < length - 1; outLoop++) {
            minIndex = outLoop;
            for (int innerLoop = outLoop + 1;innerLoop < length; innerLoop++) {
                if (array[innerLoop] < array[minIndex]) {
                    minIndex = innerLoop;
                }
            }
            swap(array, outLoop, minIndex);
        }
    }
    
    private static void swap(final int[] array, final int left, final int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}
插入排序

插入排序的精髓在于先令局部有序,先令左邊一部分數據有序,然后這部分有序的元素的下一位再與這些有序的元素比較,尋找合適自己站立的位置,插隊排進去,插隊也意味著右邊的有序元素要挪動身子。
一下提供基于for循環和while循環的兩種插入排序實現方式:

/**
 *
 *
 * @author beanlam
 * @date 2016年3月9日 下午11:26:20
 * @version 1.0
 *
 */
public class SimpleSort {
    public static void insertionSort(final int[] array) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException("array");
        }
        
        int length = array.length;
        for (int outLoop = 1; outLoop < length; outLoop++) {
            int temp = array[outLoop];
            for (int innerLoop = outLoop - 1; innerLoop >= 0; innerLoop--) {
                if (array[innerLoop] > temp) {
                    array[innerLoop + 1] = array[innerLoop];
                    if (innerLoop == 0) {
                        array[innerLoop] = temp;
                    }
                } else {
                    array[innerLoop + 1] = temp;
                    break;
                }
            }
        }
    }
    
    public static void insertionSort1(final int[] array) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException("array");
        }
        
        int length = array.length;
        int temp;
        int innerLoop;
        for (int outLoop = 1; outLoop < length; outLoop++) {
            temp = array[outLoop];
            innerLoop = outLoop;
            while (innerLoop > 0 && array[innerLoop - 1] >= temp) {
                array[innerLoop] = array[innerLoop-1];
                --innerLoop;
            }
            array[innerLoop] = temp;
        }
    }
     
    private static void swap(final int[] array, final int left, final int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}
三種排序的效率比較

假設需要比較的數組中有N個元素,
冒泡排序中,需要掃描N-1趟,每掃描一趟就要多次對兩個元素做比較,并且在必要時需要對兩個元素做位置的交換,由于數據是隨機的,所以平均下來,一趟中大概有一半被掃描的數據需要作位置的交換。
第1趟需要N-1次比較,第2趟需要N-2次比較,以此類推,總共需要N(N-1)/2趟比較,而元素的交換次數平均下來需要做NN/4次。

選擇排序和冒泡排序進行了相同次數的比較N*(N-1)/2,但每一趟只有一次交換,甚至沒有任何交換。因此,選擇排序比冒泡排序更有效率,因為它減少了很多交換。

插入排序卻又要比選擇排序更有效率一點,因為第1趟排序中,它最多比較1次,第2趟排序中,最多比較2次, 依次類推,最后一趟,最多比較N-1次,
平均只有全體數據的一半被比較,因此比較的次數為N*(N-1)/4,與冒泡和選擇排序不同的是,插入排序不需要交換數據,只是把一個值賦給數組的某一個下標,賦值的速度比交換數據的速度要快很多,因此插入排序比選擇排序和冒泡排序更有效率。

回到大O表示法

大O表示法只是一個粗略的估算值,它關注與隨著數據量N的增大,算法速度的變化。

對于數組某個下標的賦值,算法消耗的時間是個常數K
對于線性的查找,算法的消耗時間與N成正比。
對于二分查找,算法消耗時間與log(N)成正比。

大O表示法通常會忽略常數,因為它關注的是算法的消耗時間隨著N的變化而怎么變化。常數通常與處理器芯片或者編譯器有關。

在上面的三種排序中,它們的效率為用大O表示法來表示都是O(N^2),但實際上按比較的次數和交換的次數來考慮,插入排序效率高于選擇排序,選擇排序效率高于冒泡排序。

大O表示法常見的基于N的走勢圖如下圖所示:

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/65597.html

相關文章

  • 排序Java實現(遞歸方式&amp;非遞歸方式)

    摘要:很早就學習了堆排序但當時沒有用代碼實現,現在再去想實現已經忘光光啦,于是就去網上搜了一番,發現沒有一篇我能認真看完的文章,沒辦法就是沒耐心,就是笨唄。。。 很早就學習了堆排序但當時沒有用代碼實現,現在再去想實現已經忘光光啦┑( ̄Д  ̄)┍,于是就去網上搜了一番,發現沒有一篇我能認真看完的文章,沒辦法就是沒耐心,就是笨唄。。。好了,言歸正傳= ̄ω ̄= 了解概念 首先明白什么是堆,什么是完...

    jzman 評論0 收藏0
  • 泛化&amp;泛化數據集&amp;實驗

    摘要:泛化泛化數據集實驗泛化過擬合的風險泛化泛化能力是指機器學習算法對新鮮樣本的適應能力。機器學習的基本沖突是適當擬合我們的數據,但也要盡可能簡單地擬合數據。使用測試集再次檢查該模型。特征通常在正常范圍內,其中第百分位數的值約為。 泛化&泛化數據集&實驗 泛化 (Generalization):過擬合的風險 泛化:泛化能力(generalization ability)是指機器學習算法對新...

    SimpleTriangle 評論0 收藏0
  • react+mobx 構建H5制作工具項目經驗總結

    摘要:三性能優化處理做工具類的項目,性能是非常大的挑戰,我總結了以下幾個常見的性能優化點數據緩存。防抖,節流,事件委托內存釋放。 內容大綱: 1、功能介紹 2、技術架構 3、性能優化 4、細節分享 5、開源說明 一、項目功能介紹 很久沒寫過技術類的文章了,這次給大家分享一個近期的項目,采用react+mobx+jquery構建的大型工具類項目。查看項目網址。 如果用過易企秀,maka或者...

    用戶84 評論0 收藏0
  • react+mobx 構建H5制作工具項目經驗總結

    摘要:三性能優化處理做工具類的項目,性能是非常大的挑戰,我總結了以下幾個常見的性能優化點數據緩存。防抖,節流,事件委托內存釋放。 內容大綱: 1、功能介紹 2、技術架構 3、性能優化 4、細節分享 5、開源說明 一、項目功能介紹 很久沒寫過技術類的文章了,這次給大家分享一個近期的項目,采用react+mobx+jquery構建的大型工具類項目。查看項目網址。 如果用過易企秀,maka或者...

    Aceyclee 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<