關于《算法》判斷一個算法的資料規模不要盲目的判斷

對于判斷一段代碼的資料規模很多時候是可以看到捷徑的比如有兩個n循環，其中後面一個循環和n是成正相關，此時前一個n和後一個n互相嵌套，是以此時的數量級上表示應該是O(n^2)級别。

但是會有的時候後還是有特例的 比如兩個嵌套，中間嵌套層并沒有出現n，隻是一個常數，此時就不能一概而論的認為應該是O（n^2）級别複雜度的代碼。

利用二分查找法尋找判斷O(nlogn) 級别算法的資料規模，以下為例：

#include "binarySearch.h"
int binarySearch(int arr[],int n,int target){
    int l = 0,r = n-1;
    while(l<=r){
        int mid = l + (r-l)/2;
        if(arr[mid] == target ) return mid;
        if(arr[mid] > target) r = mid;
        else l = mid +1;
    }
    return -1;
}           

每一次查找都是在尋找到的結果中的一半的結果中查找，如果能夠找到結束，沒有辦法找到的話就是在1/2,1/4....中查找，這正好是對數的定義。是以這種層次就是對數級别的數量級函數查找。

對于Log10和Log2的數量級之間能夠相差多少呢？其實在高中教材中關于對數的推導有着相關的公式，兩者之間隻是常數級别的差距。是以這個對數的底并不是很重要是以簡單的忽略掉這個對數的底，就可以統一的成為O(nlogn)。

我們可以根據這個複雜度做出相關的實驗：

我們會遇到這種情況：我們以為自己寫出了一個O(Logn)級别的算法，但是，實際上卻是O(n^2)級别的算法，很多時候線上判題的網站就會産生問題。

為了解決這個問題，這時就需要觀察實驗趨勢，将資料規模提高兩倍看時間的變化。

測試規模為O(logn)級别的測試使用代碼：

namespace MyAlgorithmTester{
    //O(logN)
    int binarySearch(int arr[]){
        
        int l = 0,r = n-1;
        while( l<=r){
            int mid = l + (r-l)/2;
            if( arr[mid]==target) return mid;
            if( arr[mid]>target) r = mid -1;
            else l = mid+1;
        }
        return -1;
    }
}           

這是一個簡單的O(Logn)級别的算法 對于基礎的算法規模來說這是一個非常好了解的低數量級的代碼；

int main(){
    //資料規模倍乘測試findMax
    //O(n)
    for(int i = 10; i<= 26;i++){
        int n = pow(2,i);
        int *arr =MyUtil::generateRandomArray(n,0,1000000000);

        clock_t startTime = clock();
        MyAlgorithmTester::findMax(arr,n);
        clock_t endTime = clock();

        cout<<"data size 2^"<<i<<" = "<<n<<"t";
        cout<<"Time cost:"<<double(endTime-startTime);

        delete[] arr;
    }
}           

根據我們獲得的資訊将各種資料規模的算法依次進行排列 我們可以得到很多個結果：

獲得的結論如下：

1）每一行的結果都比上一行的資料結果翻了兩倍，也就是說資料規模每增加一個數量級就會在時間上增加一倍；

2）由此可以看出這個資料規模是O(n)級别；

然後我們看一個O（n^2）級别的算法：

int main(){
    //資料規模備乘測試selectionSort
    //O(n^2)
    cout<<"Test for selectionSort:"<<endl;
    for(int i = 10; i<=15; i++){
        
        int n = pow(2,i);
        int *arr = MyUtil::generateRandomArray(n,0,100000000);
        
        clock_t startTime = clock();
        MyAlgorithmTester::selectionSort(arr,n);
        clock_t endTime = clock();
        
        cout<<"data size 2^"<<i<<"="<<n<<"\t";
        cout<<"Time out:"<<double(endTime-startTime)/CLOCKS_PER_SEC<<endl;
        
        delete[] arr;
    }
    return 0;
}           

由于O(N^2)這個數量級太高了是以我們隻運作到15這個數；

得出的結果如下圖所示：

因為我們所使用的是O（n^2）這個級别 是以我們獲得的結果也應該是下面的結果是上面的4倍。

結論：将順序查找問題轉換為二分查找的問題使用效率會大大提升。