麻豆亚洲国产成人精品无码区,成人无码av片在线观看

面試中的時間復(fù)雜度分析

到底什么是大O

常見算法復(fù)雜度

和a.b.c.d這些常數(shù)項(xiàng)關(guān)系不大。主要還是看它是哪個層級的。

算法A：O(n) 所需執(zhí)行指令數(shù)：10000n
算法B：O(n^2) 所需執(zhí)行指令數(shù)：10n^2

n的規(guī)模逐漸增大。算法a.b的指令數(shù)變化。

對比

當(dāng)n大于某個臨界點(diǎn)，a一定會超過b。這是量級上的差距。

復(fù)雜度很高的算法可能有前面的優(yōu)勢，在數(shù)據(jù)量很小的時候有意義。

對于所有高級的排序算法，當(dāng)數(shù)據(jù)規(guī)模小到一定程度，我們都可以使用插入排序法進(jìn)行優(yōu)化。10%-15%。細(xì)節(jié)優(yōu)化。

不同時間復(fù)雜度隨著數(shù)據(jù)規(guī)模的增大，

在學(xué)術(shù)界，嚴(yán)格地講，O(f(n))表示算法執(zhí)行的上界
歸并排序算法的時間復(fù)雜度是O(nlogn)的，同時也是O(n^2)
c.nlogn < a.n^2

在業(yè)界，我們就使用O來表示算法執(zhí)行的最低上界
我們一般不會說歸并排序是O(n^2)的

以主導(dǎo)作用的為準(zhǔn)：

O( nlogn + n ) = O( nlogn )

O( nlogn + n^2 ) = O( n^2 )

上面的公式要求算法處理的n是一樣的。

O( AlogA + B )
O( AlogA + B^2 )

上面這種不能省略

對鄰接表實(shí)現(xiàn)的圖進(jìn)行遍歷：
時間復(fù)雜度：O( V + E ) V是頂點(diǎn)個數(shù)，E是邊的個數(shù)。

稠密圖，甚至完全圖。E是近乎V^2級別。

一個時間復(fù)雜度的問題

有一個字符串?dāng)?shù)組，將數(shù)組中的每一個字符串按照字母序排序；之后再將整個字符串?dāng)?shù)組按照字典序排序。整個操作的時間復(fù)雜度？

錯誤答案

每個字符串n*nlogn + 整個字符串?dāng)?shù)組：nlogn

錯誤：1. 字符串的長度和數(shù)組長度混淆

假設(shè)最長的字符串長度為s；數(shù)組中有n個字符串
對每個字符串排序：O(slogs)
將數(shù)組中的每一個字符串按照字母序排序：O(n*slog(s))

將整個字符串?dāng)?shù)組按照字典序排序：O(s*nlog(n))

解釋：對于排序算法時間復(fù)雜度理解：
nlogn 是比較的次數(shù)。對整型數(shù)組排序只需要nlogn次比較。因?yàn)閮蓚€整數(shù)之間比較

O(1)。兩個字符串比較不一樣O(s)。

O(n*slog(s)) + O(s*nlog(n)) = O( n*s*logs + s*n*logn )
                                            = O( n*s*(logs+logn) )

算法復(fù)雜度在有些情況是用例相關(guān)的

插入排序算法 O(n^2)

最差情況：O(n^2)
最好情況：O(n)：近乎有序
平均情況：O(n^2)

快速排序算法 O(nlogn)

最差情況：O(n^2) 不隨機(jī)。有序
最好情況：O(nlogn) 隨機(jī)化標(biāo)定點(diǎn)
平均情況：O(nlogn)

嚴(yán)謹(jǐn)算法最好最差平均。我們經(jīng)常關(guān)注的是大多數(shù)。
極端情況心里有數(shù)就行了。

數(shù)據(jù)規(guī)模的概念

對 10^5 的數(shù)據(jù)進(jìn)行選擇排序，結(jié)果計(jì)算機(jī)假死？

int main() {

    for( int x = 1 ; x <= 9 ; x ++ ){
        //10的x次方的冪運(yùn)算
        int n = pow(10, x);
        
        clock_t startTime = clock();

        int sum = 0;
        for( int i = 0 ; i < n ; i ++ )
            sum += i;
        clock_t endTime = clock();

        cout<<"10^"<<x<<" : "<<double(endTime - startTime)/CLOCKS_PER_SEC<<" s"<<endl;
    }
    return 0;
}

運(yùn)行結(jié)果

如果要想在1s之內(nèi)解決問題：

O(n^{2)的算法可以處理大約10}4級別的數(shù)據(jù)；
O(n)的算法可以處理大約10^8級別的數(shù)據(jù)；
O(nlogn)的算法可以處理大約10^7級別的數(shù)據(jù)

因?yàn)槲覀儎偛诺牟僮骱芎唵?，就是簡單的加法。所以正常還需要低估一點(diǎn)。

空間復(fù)雜度

多開一個輔助的數(shù)組：O(n)

多開一個輔助的二維數(shù)組：O(n^2)
多開常數(shù)空間：O(1):原地?cái)?shù)組排序

遞歸調(diào)用是有空間代價的：
在遞歸調(diào)用前的函數(shù)壓入系統(tǒng)棧中的。

空間復(fù)雜度O(1):
不管n有多大，只開辟了ret。索引i。
不會增加空間。

int sum1( int n ){

    assert( n >= 0 );
    int ret = 0;
    for( int i = 0 ; i <= n ; i ++ )
        ret += i;
    return ret;
}

空間復(fù)雜度O(n)
深度是n，系統(tǒng)棧中就要裝載n個狀態(tài)。
遞歸深度就是遞歸的空間復(fù)雜度

int sum2( int n ){

    assert( n >= 0 );
    if( n == 0 )
        return 0;

    return n + sum2(n-1);
}

常見的復(fù)雜度分析

O(1)
沒有數(shù)據(jù)規(guī)模的變化

// O(1)
void swapTwoInts( int &a , int &b ){
    int temp = a;
    a = b;
    b = temp;
    return;
}

O(n)
循環(huán)操作次數(shù)為c.n。c是個常數(shù)不一定為大于1的數(shù)

// O(n) Time Complexity
int sum( int n ){

    int ret = 0;
    for( int i = 0 ; i <= n ; i ++ )
        ret += i;
    return ret;
}

O(n)
循環(huán)次數(shù)為1/2 n次
字符串翻轉(zhuǎn)。abc-cba.第一個和倒數(shù)第一個。第2個和倒數(shù)第二個
掃描一半就交換完了：1/2*n次swap操作：O(n)

void reverse( string &s ){

    int n = s.size();
    for( int i = 0 ; i < n/2 ; i ++ )
        swap( s[i] , s[n-1-i] );
    return;
}

O(n^2)
選擇排序法。O(n^2)
雙重循環(huán): 第一重到n。第二重到n。都是+1.
所執(zhí)行的指令數(shù)和n^2成比例。

i = 0;j執(zhí)行了n-1次

(n-1) + (n-2) + (n-3) + … + 0
= (0+n-1)*n/2
= (1/2)n*(n-1)
= 1/2*n^2 - 1/2*n
= O(n^2)

等差數(shù)列求和

// O(n^2) Time Complexity
void selectionSort(int arr[], int n){

    for(int i = 0 ; i < n ; i ++){
        int minIndex = i;
        for( int j = i + 1 ; j < n ; j ++ )
            if( arr[j] < arr[minIndex] )
                minIndex = j;

        swap( arr[i] , arr[minIndex] );
    }
}

30n次基本操作：O(n)
因?yàn)榈诙友h(huán)是固定的不受n影響的。

// O(n) Time Complexity
void printInformation(int n){

    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= 30 ; j ++ )
            cout<<"Class "<<i<<" - "<<"No. "<<j<<endl;
    return;
}

o(logn)
對有序數(shù)組找到中間元素來判斷元素和中間元素的關(guān)系。
如果沒有查找到，都可以扔掉一半的元素。

二分查找法

n經(jīng)過幾次除以2等于1.log2n = O(logn)

// O(logn) Time Complexity
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 - 1;
        else l = mid + 1;
    }
    return -1;
}

O(logn)

n經(jīng)過幾次“除以10”操作后，等于0？
log10n = O(logn)
while循環(huán)中每次除以10，直到0結(jié)束。
reverse(s)復(fù)雜度：1/2 n次的交換操作。s字符串有多少位。與n一致。

string intToString( int num ){

    string s = "";
    string sign = "+";
    if( num < 0 ){
        num = -num;
        sign = "-";
    }

    while( num ){
        s += '0' + num%10;
        num /= 10;
    }

    if( s == "" )
        s = "0";

    reverse(s);
    if( sign == "-" )
        return sign + s;
    else
        return s;
}

常數(shù)差距

2n 與 3n的常數(shù)級差別

O(nlogn)

第二重循環(huán)就是n
第一重size+=size就是乘以2.log2n

// O(nlogn)
void hello(int n){

    for( int sz = 1 ; sz < n ; sz += sz )
        for( int i = 1 ; i < n ; i ++ )
            cout<<"Hello, Algorithm!"<<endl;
}

O(sqrt(n))
x從n走一直走到根號n結(jié)束

// O(sqrt(n)) Time Complexity
bool isPrime( int num ){

    for( int x = 2 ; x*x <= num ; x ++ )
        if( num%x == 0 )
            return false;
    return true;
}

bool isPrime2( int num ){

    if( num <= 1 ) return false;
    if( num == 2 ) return true;
    if( num%2 == 0 ) return false;

    for( int x = 3 ; x*x <= num ; x += 2 )
        if( num%x == 0 )
            return false;

    return true;
}

復(fù)雜度實(shí)驗(yàn)。

我們自以為寫出了一個O(nlogn)的算法，但實(shí)際是O(n^2)的算法？

如果要想在1s之內(nèi)解決問題：

O(n^{2)的算法可以處理大約10}4級別的數(shù)據(jù)；
O(n)的算法可以處理大約10^8級別的數(shù)據(jù)；
O(nlogn)的算法可以處理大約10^7級別的數(shù)據(jù)

前面的常數(shù)差距有可能很大。

實(shí)驗(yàn)，觀察趨勢：

每次將數(shù)據(jù)規(guī)模提高兩倍，看時間的變化

四個不同復(fù)雜度的算法。

namespace MyAlgorithmTester{

    // O(logN)
    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 - 1;
            else l = mid + 1;
        }

        return -1;
    }

    // O(N)
    int findMax( int arr[], int n ){

        assert( n > 0 );

        int res = arr[0];
        for( int i = 1 ; i < n ; i ++ )
            if( arr[i] > res )
                res = arr[i];

        return res;
    }

    // O(NlogN) 自底向上
    void __merge(int arr[], int l, int mid, int r, int aux[]){

        for(int i = l ; i <= r ; i ++)
            aux[i] = arr[i];

        int i = l, j = mid+1;
        for( int k = l ; k <= r; k ++ ){

            if( i > mid )   { arr[k] = aux[j]; j ++;}
            else if( j > r ){ arr[k] = aux[i]; i ++;}
            else if( aux[i] < aux[j] ){ arr[k] = aux[i]; i ++;}
            else                      { arr[k] = aux[j]; j ++;}
        }
    }

    void mergeSort( int arr[], int n ){

        int *aux = new int[n];
        for( int i = 0 ; i < n ; i ++ )
            aux[i] = arr[i];

        for( int sz = 1; sz < n ; sz += sz )
            for( int i = 0 ; i < n ; i += sz+sz )
                __merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1), aux );

        delete[] aux;

        return;
    }

    // O(N^2) 選擇排序
    void selectionSort( int arr[], int n ){

        for(int i = 0 ; i < n ; i ++){
            int minIndex = i;
            for( int j = i + 1 ; j < n ; j ++ )
                if( arr[j] < arr[minIndex] )
                    minIndex = j;

            swap( arr[i] , arr[minIndex] );
        }

        return;
    }
}

生成測試用例的代碼：

namespace MyUtil {

    int *generateRandomArray(int n, int rangeL, int rangeR) {

        assert( n > 0 && rangeL <= rangeR );

        int *arr = new int[n];

        srand(time(NULL));
        for (int i = 0; i < n; i++)
            arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
        return arr;
    }

    int *generateOrderedArray(int n) {

        assert( n > 0 );

        int *arr = new int[n];

        for (int i = 0; i < n; i++)
            arr[i] = i;
        return arr;
    }

}

測試是不是O(n)級別的

int main() {

    // 數(shù)據(jù)規(guī)模倍乘測試findMax
    // O(n)
    cout<<"Test for findMax:"<<endl;
    for( int i = 10 ; i <= 26 ; i ++ ){

        int n = pow(2,i);
        int *arr = MyUtil::generateRandomArray(n, 0, 100000000);

        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)/CLOCKS_PER_SEC<<endl;

        delete[] arr;
    }

    return 0;
}

運(yùn)行結(jié)果：

運(yùn)行結(jié)果

n增加了兩倍。時間也大致增加兩倍，所以該算法為O(n)級別的。

測試是不是O(n^2)

int main() {

    // 數(shù)據(jù)規(guī)模倍乘測試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 cost: "<<double(endTime - startTime)/CLOCKS_PER_SEC<<endl;

        delete[] arr;
    }

    return 0;
}

運(yùn)行結(jié)果：大約4倍

數(shù)據(jù)量n增加了2倍。時間增加了4倍。

int main() {

    // 數(shù)據(jù)規(guī)模倍乘測試binarySearch
    // O(logn)
    cout<<"Test for binarySearch:"<<endl;
    for( int i = 10 ; i <= 28 ; i ++ ){

        int n = pow(2,i);
        int *arr = MyUtil::generateOrderedArray(n);

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

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

        delete[] arr;
    }

    return 0;
}

復(fù)雜度試驗(yàn)

 log2N / logN
=  (log2 + logN)/logN
= 1 + log2/logN

當(dāng)數(shù)據(jù)規(guī)模變大兩倍。運(yùn)行效率增加1.幾倍。

運(yùn)行結(jié)果：

運(yùn)行結(jié)果，變化小

順序查找轉(zhuǎn)換為二分查找，大大提高效率

int main() {

    // 數(shù)據(jù)規(guī)模倍乘測試mergeSort
    // O(nlogn)
    cout<<"Test for mergeSort:"<<endl;
    for( int i = 10 ; i <= 24 ; i ++ ){

        int n = pow(2,i);
        int *arr = MyUtil::generateRandomArray(n,0,1<<30);

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

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

        delete[] arr;
    }

    return 0;
}

運(yùn)行結(jié)果：

大約兩倍

遞歸算法的復(fù)雜度分析

不是有遞歸的函數(shù)就一定是O(nlogn)!

歸并排序 & 快速排序

遞歸中進(jìn)行一次遞歸調(diào)用的復(fù)雜度分析：

二分查找的遞歸實(shí)現(xiàn)：
左半邊或者右半邊。無論選那邊都只進(jìn)行一次
每次減半，遞歸調(diào)用的深度為logn，處理問題的復(fù)雜度為O(1)

// binarySearch
int binarySearch(int arr[], int l, int r, int target){

    if( l > r )
        return -1;

    int mid = l + (r-l)/2;
    if( arr[mid] == target )
        return mid;
    else if( arr[mid] > target )
        return binarySearch(arr, l, mid-1, target);
    else
        return binarySearch(arr, mid+1, r, target);

}

如果遞歸函數(shù)中，只進(jìn)行一次遞歸調(diào)用，
遞歸深度為depth;
在每個遞歸函數(shù)中，時間復(fù)雜度為T;
則總體的時間復(fù)雜度為O( T * depth )

求和遞歸實(shí)現(xiàn)
遞歸深度：n
時間復(fù)雜度：O(n)

// sum
int sum( int n ){

    assert( n >= 0 );

    if( n == 0 )
        return 0;
    return n + sum(n-1);
}

計(jì)算x的n次方的冪運(yùn)算
我在計(jì)算x的n次方時候，如果知道n.2次方
就是x^n/2 * x^n/2

// pow2
double pow( double x, int n ){

    assert( n >= 0 );

    if( n == 0 )
        return 1.0;

    double t = pow(x, n/2);
    //奇數(shù)
    if( n%2 )
        return x*t*t;

    return t*t;
}

遞歸深度：logn
時間復(fù)雜度：O(logn)

遞歸中進(jìn)行多次遞歸調(diào)用
在進(jìn)行一次遞歸調(diào)用，深度就是次數(shù)。

遞歸樹

20 + 21 + 22 + 23 + … + 2n
= 2n+1 - 1
= O(2^n)

指數(shù)級的算法：非常慢。n在20左右。30就。
剪枝操作：動態(tài)規(guī)劃。人工智能：搜索樹

// f
int f(int n){

    assert( n >= 0 );

    if( n == 0 )
        return 1;

    return f(n-1) + f(n-1);
}

歸并排序n=8

當(dāng)n等于8時，層數(shù)為3層。每一層處理的數(shù)據(jù)規(guī)模越來越小
一個分成logn層。每一層相加的總體規(guī)模還是n

// mergeSort
void mergeSort(int arr[], int l, int r){

    if( l >= r )
        return;

    int mid = (l+r)/2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid+1, r);
    merge(arr, l, mid, r);
}

分治算法。

主定理

規(guī)定了遞歸情況所有的時間復(fù)雜度可能。

均攤復(fù)雜度分析 Amortized Time

一個算法復(fù)雜度相對較高，但是它是為了方便其他的操作。
比較高的會均攤到整體。

動態(tài)數(shù)組（Vector）

template <typename T>
class MyVector{

private:
    T* data;
    int size;       // 存儲數(shù)組中的元素個數(shù)
    int capacity;   // 存儲數(shù)組中可以容納的最大的元素個數(shù)

    // O(n)：一重循環(huán)。
    void resize(int newCapacity){

        assert( newCapacity >= size );
        T *newData = new T[newCapacity];
        for( int i = 0 ; i < size ; i ++ )
            newData[i] = data[i];
        delete[] data;

        data = newData;
        capacity = newCapacity;
    }

public:
    MyVector(){

        data = new T[100];
        size = 0;
        capacity = 100;
    }

    ~MyVector(){

        delete[] data;
    }

    // Average: O(1)
    void push_back(T e){

        //動態(tài)數(shù)組
        if( size == capacity )
            resize( 2* capacity );

        data[size++] = e;
    }

    // O(1)
    T pop_back(){

        assert( size > 0 );
        size --;

        //size是從0開始的。也就是0號索引size為1.
        //所以要拿到最后一個元素，就得size-1
        return data[size];
    }

};

假設(shè)當(dāng)前數(shù)組容量為n

均攤

第n+1次會花費(fèi)O(n)但是會把這n分?jǐn)偟角懊鎛次操作。也就是變成了O(2)
還是常數(shù)O(1)級的。
resize是有條件的，而不是每次都調(diào)用。

int main() {

    for( int i = 10 ; i <= 26 ; i ++ ){

        int n = pow(2,i);

        clock_t startTime = clock();
        MyVector<int> vec;
        for( int i = 0 ; i < n ; i ++ ){
            vec.push_back(i);
        }
        clock_t endTime = clock();

        cout<<n<<" operations: \t";
        cout<<double(endTime - startTime)/CLOCKS_PER_SEC<<" s"<<endl;
    }

    return 0;
}

基本滿足2倍關(guān)系

刪除元素縮小空間。

刪除

每次普通刪除時間復(fù)雜度都為O(1)

只剩下n個。這次resize n 刪除這個元素為1

臨界點(diǎn)震蕩無法均攤

重復(fù)這個過程，無法均攤，復(fù)雜度為O(n)

當(dāng)元素個數(shù)為數(shù)組容量的1/4時，resize.為再添加元素留出余地

template <typename T>
class MyVector{

private:
    T* data;
    int size;       // 存儲數(shù)組中的元素個數(shù)
    int capacity;   // 存儲數(shù)組中可以容納的最大的元素個數(shù)

    // O(n)
    void resize(int newCapacity){

        assert( newCapacity >= size );
        T *newData = new T[newCapacity];
        for( int i = 0 ; i < size ; i ++ )
            newData[i] = data[i];
        delete[] data;

        data = newData;
        capacity = newCapacity;
    }

public:
    MyVector(){

        data = new T[100];
        size = 0;
        capacity = 100;
    }

    ~MyVector(){

        delete[] data;
    }

    // Average: O(1)
    void push_back(T e){

        if( size == capacity )
            resize( 2* capacity );

        data[size++] = e;
    }

    // Average: O(1)
    T pop_back(){

        assert( size > 0 );
        T ret = data[size-1];
        size --;
        if( size == capacity/4 )
            resize( capacity/2 );
        //resize之后會把data[size]元素抹掉
        return ret;
    }

};

運(yùn)行結(jié)果

均攤復(fù)雜度：

動態(tài)數(shù)組
動態(tài)棧
動態(tài)隊(duì)列

成熟丰满熟妇高潮XXXXX,人妻无码AV中文系列久久兔费 ,国产精品一国产精品,国精品午夜福利视频不卡麻豆

玩轉(zhuǎn)算法面試：（二）面試中的復(fù)雜度分析

面試中的時間復(fù)雜度分析

到底什么是大O

數(shù)據(jù)規(guī)模的概念

常見的復(fù)雜度分析

復(fù)雜度實(shí)驗(yàn)。

遞歸算法的復(fù)雜度分析

均攤復(fù)雜度分析 Amortized Time

刪除元素縮小空間。

成熟丰满熟妇高潮XXXXX,人妻无码AV中文系列久久兔费 ,国产精品一国产精品,国精品午夜福利视频不卡麻豆

玩轉(zhuǎn)算法面試：（二）面試中的復(fù)雜度分析

面試中的時間復(fù)雜度分析

到底什么是大O

數(shù)據(jù)規(guī)模的概念

常見的復(fù)雜度分析

復(fù)雜度實(shí)驗(yàn)。

遞歸算法的復(fù)雜度分析

均攤復(fù)雜度分析 Amortized Time

刪除元素縮小空間。

刪除元素縮小空間。