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

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

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

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

Time Limit Exceeded

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

有一個你想要測的方法a；

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

實現(xiàn)一個隨機樣本產(chǎn)生器；

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

把方法a和方法b比對多次來驗證方法a是否正確；

如果有一個樣本使得比對出錯，打印樣本分析是哪個方法出錯；

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

其中要注意以下幾點：

隨機產(chǎn)生的樣本應(yīng)該是小數(shù)據(jù)集，但是要進行多次(10w+)的對比。小數(shù)據(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);
        }
    }
}

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

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

實現(xiàn)一個隨機樣本產(chǎn)生器

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

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

// 判斷兩個數(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進行多次的比對

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

當(dāng)樣本數(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);

}

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

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

數(shù)組排序

Java版本

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