常見算法設計方法-分治法

分治法(Devide & Conquer)

1. 常見步驟

• Devide
  把一個問題的特殊實例劃分成若干個子問題
• Conquer
  遞歸地解決每個子問題
• Combine
  將每個子問題的答案組合成最終答案

2. 舉例分析

歸並排序就是常見的一種采用“分治法”進行設計的算法，以下先給出具體的C#版代碼示例

    /// <summary>
    ///     對列表進行遞歸排序
    /// </summary>
    /// <param name="list">待排序數組</param>
    /// <returns></returns>
    public static List<int> Sort(List<int> list)
    {
        if (list.Count <= 1)
            return list;
        var mid = list.Count/2;
        var left = new List<int>(); 
        var right = new List<int>(); 
        
        // Devide
        for (var i = 0; i < mid; i++)
            left.Add(list[i]);
        for (var j = mid; j < list.Count; j++)
            right.Add(list[j]);
        // Conquer
        left = Sort(left);
        right = Sort(right);

        // Combine
        return Merge(left, right);
    }

    /// <summary>
    ///     合並已經排序好的兩個List
    /// </summary>
    /// <param name="left">Left List</param>
    /// <param name="right">Right List</param>
    /// <returns></returns>
    private static List<int> Merge(List<int> left, List<int> right)
    {
        var temp = new List<int>();
        while ((left.Count > 0) && (right.Count > 0))
        {
            if (left[0] <= right[0])
            {
                temp.Add(left[0]);
                left.RemoveAt(0);
            }
            else
            {
                temp.Add(right[0]);
                right.RemoveAt(0);
            }
        }

        if (left.Count > 0)
        {
            foreach (int item in left)
            {
                temp.Add(item);
            }
        }
            
        if (right.Count > 0)
        {
            foreach (int item in right)
            {
                temp.Add(item);
            }
        }
        
        return temp;

    }

分析這個算法可以發現，歸並算法的遞歸部分在於不斷地將待排序數組分為左右兩個等長的數組直至左右列表中都只含有一個元素，再繼續進行Merge操作，前者遞歸所花費的時間可以簡單表示成2T(n/2)，後者排序可以認為是θ(n)，則總時間可以表示成T(n)=2T(n/2)+θ(n)。

平均情況下，定義的T(n)=輸入規模為n之下時所有可能輸入的期望時間，θ是漸進符號一種，大家可以簡單認為對於輸入n，f(n)存在精確上下界

接下來在計算時間復雜度的時候，針對這個優雅的時間函數我們可以有兩種解決辦法，第一種是判斷整個遞歸樹的長度和葉節點的個數，第二種則是直接套用主定理公式進行分析。這裡我們采用第二種主定理進行分析。

這裡是對主定理的相關說明

針對T(n)=aT(n/b)+f(n)的函數式子（a≥1,b>1），我們可以知道歸並排序算法的函數符合主定理的第二種情況，即如果存在常數k ≥ 0，有
f(n)=θ(n^(㏒{b}a((㏒n)^k))，則有T(n)=θ(n^(㏒{b}a((㏒n)^(k+1)))。這裡的k=0，則歸並算法最終的時間復雜度T(n)=θ(n㏒n)

額外補充一個二分法實例

    /// <summary>
    ///     二分法查找
    /// </summary>
    /// <param name="list">傳入的有序列表</param>
    /// <param name="beginIndex">起始位置</param>
    /// <param name="endIndex">終止位置</param>
    /// <param name="x">需要查找的x</param>
    /// <returns>返回的列表索引</returns>
    public static int BinarySearch(List<int> list, int beginIndex, int endIndex, int x)
    {
        if ((x > list.LastOrDefault()) | (x < list.FirstOrDefault()))
            return -1;

        if (x == list[beginIndex])
            return beginIndex;

        if (x == list[endIndex])
            return endIndex;

        var mid = (beginIndex + endIndex)/2;
        if (x == list[mid])
            return mid;
        return x > list[mid] ? BinarySearch(list, mid, endIndex, x) : BinarySearch(list, beginIndex, mid, x);

    }