摘要：對于一個(gè)數(shù)組的排序，如果筆試中要求的時(shí)間復(fù)雜度是，但是你卻寫了一個(gè)冒泡排序的算法交上去了，這時(shí)就會提示而在對數(shù)器中，我們要求的絕對正確的算法是沒有時(shí)間和空間復(fù)雜度的限制的，唯一的要求是確保絕對正確。

對數(shù)器是通過用大量測試數(shù)據(jù)來驗(yàn)證算法是否正確的一種方式。在算法筆試的時(shí)候，我們經(jīng)常只能確定我們寫出的算法在邏輯上是大致正確的，但是誰也不能一次性保證絕對的正確。特別是對于一些復(fù)雜的題目，例如貪心算法，我們往往無法在有限時(shí)間內(nèi)用數(shù)學(xué)公式來推導(dǎo)證明我們程序的正確性。而且在線的OJ一般只會給出有數(shù)的幾個(gè)簡單的samples，可能我們的算法在這些簡單的samples偶然通過了，但是在一些復(fù)雜的samples處卻出現(xiàn)了問題。這時(shí)我們無法使用復(fù)雜的samples來分析調(diào)試我們的代碼，人工設(shè)計(jì)樣例來測試代碼的效率又太低，而且不能確保考慮各種特殊情況。因此，能隨機(jī)產(chǎn)生不同情況的數(shù)據(jù)的對數(shù)器就派上了用場。

對數(shù)器，簡而言之，就是一個(gè)絕對正確的方法和能產(chǎn)生大量隨機(jī)樣例的隨機(jī)器的組合。看到這里，有些童鞋有疑問了。既然我們知道了絕對正確的方法，直接用這個(gè)方法不就好了嘛？

請注意，算法追求的不是解決問題，而是高效率的解決問題。對于一個(gè)數(shù)組的排序，如果筆試中要求的時(shí)間復(fù)雜度是$O(NlogN)$$，但是你卻寫了一個(gè)冒泡排序的算法交上去了，這時(shí)OJ就會提示：

Time Limit Exceeded

而在對數(shù)器中，我們要求的絕對正確的算法是沒有時(shí)間和空間復(fù)雜度的限制的，唯一的要求是確保絕對正確。因?yàn)橹挥薪^對正確，我們才能通過樣例的比對，發(fā)現(xiàn)我們的代碼是在哪里出了錯(cuò)誤。

有一個(gè)你想要測的方法a；

實(shí)現(xiàn)一個(gè)絕對正確但是復(fù)雜度不好的方法b；

實(shí)現(xiàn)一個(gè)隨機(jī)樣本產(chǎn)生器；

實(shí)現(xiàn)對比算法a和b的方法；

把方法a和方法b比對多次來驗(yàn)證方法a是否正確；

如果有一個(gè)樣本使得比對出錯(cuò)，打印樣本分析是哪個(gè)方法出錯(cuò)；

當(dāng)樣本數(shù)量很多時(shí)比對測試依然正確，可以確定方法a已經(jīng)正確。

其中要注意以下幾點(diǎn)：

隨機(jī)產(chǎn)生的樣本應(yīng)該是小數(shù)據(jù)集，但是要進(jìn)行多次(10w+)的對比。小數(shù)據(jù)集是因?yàn)榉奖銓Ρ确治觯啻伪葘κ且采w所有的隨機(jī)情況。

算法b要保持正確性。

冒泡排序的對數(shù)器：

要測的方法

public static void bubbleSort(int[] arr)
{
    if (arr==null || arr.length < 2)
        return;
    for (int end = arr.length - 1;end>0; end--)
    {
        for (int i = 0; i < end; i++)
        {
            if (arr[i] > arr[i+1])
                swap(arr, i, i+1);
        }
    }
}

實(shí)現(xiàn)一個(gè)絕對正確，可以復(fù)雜度不是很好的方法b

// 可以直接用一些庫函數(shù)來進(jìn)行測試
public static void rightMethod(int[] arr)
{
    Arrays.sort(arr);
}

實(shí)現(xiàn)一個(gè)隨機(jī)樣本產(chǎn)生器

// 隨機(jī)數(shù)生成器
public static int[] generateRandomArray(int size, int value)
{
//Math.random() -> double [0,1)
//(int) ((size + 1) * Math.random()) -> [0,size]整數(shù)
// 生成長度隨機(jī)[0, size]的數(shù)組
int[] arr = new int[(int) ((size+1) * Math.random())];
for (int i = 0; i < arr.length; i++)
{
    // 一個(gè)隨機(jī)數(shù)減去另一個(gè)隨機(jī)數(shù)，生成[-value, value]的隨機(jī)數(shù)
    arr[i] = (int) ((value+1) * Math.random()) - (int) (value * Math.random());
}
return arr;
}

實(shí)現(xiàn)比對的方法

// 判斷兩個(gè)數(shù)組是否相等
public static boolean isEqual(int[] arr1, int[] arr2)
{
    if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null))
        return false;
    if (arr1 == null && arr2 == null)
        return true;
    if (arr1.length != arr2.length)
        return  false;
    for (int i = 0; i < arr1.length; i++)
    {
        if (arr1[i] != arr2[i])
            return false;
    }
    return true;
}

將方法a和方法b進(jìn)行多次的比對

如果有一個(gè)樣本使得本次比對出錯(cuò)，則打印該樣本，分析方法錯(cuò)在哪里

當(dāng)樣本數(shù)量足夠多時(shí)，比對測試依然正確，則可以確定我們寫的方法a是正確的

public static void main(String[] args) 
{
    int testTime = 500000;
    int size = 10;
    int value = 100;
    boolean succeed = true;
    for (int i = 0; i < testTime; i++)
    {
        int[] arr1 = generateRandomArray(size, value);
        int[] arr2 = copyArray(arr1);
        int[] arr3 = copyArray(arr1);
        bubbleSort(arr1);
        rightMethod(arr2);
        if (!isEqual(arr1, arr2))
        {
            succeed = false;
            printArray(arr3);
            break;
        }
    }
    System.out.println(succeed ? "Nice!" : "error----");
    int[] arr = generateRandomArray(size, value);
    printArray(arr);
    bubbleSort(arr);
    printArray(arr);

}

很多童鞋進(jìn)行筆試前，都是背一些記在小本本上的代碼，然后匆匆上陣。寫出的算法的正確性完全靠OJ的判斷，當(dāng)程序卡在一個(gè)2000行的數(shù)組樣例處出現(xiàn)錯(cuò)誤時(shí)，就完全傻了......這T喵叫我怎么去進(jìn)行調(diào)試分析啊。而有對數(shù)器的小伙伴就不一樣了，由于使用的都是小樣本，出現(xiàn)錯(cuò)誤時(shí)也方面進(jìn)行分析。而且進(jìn)行了多次測試，確保覆蓋了所有的特殊情況。因此筆試前我們可以準(zhǔn)備一些對數(shù)器模版，如數(shù)組排序的對數(shù)器，鏈表的對數(shù)器等等。后續(xù)我也會更新一些對數(shù)器的模版，有java版本和python版本。

記住哦，offer都是留給有準(zhǔn)備的人~~

數(shù)組排序

Java版本

后續(xù)版本，陸續(xù)更新中.....