一区二区三区毛片网站,超碰人妻一区,99热在线播放

一、目標(biāo)：計算

??整個計算機(jī)科學(xué)的目的，都是為了實(shí)現(xiàn)高效和低耗的計算。為了理解什么是計算，我們首先來看幾個實(shí)例。

Fig. 1 實(shí)例：繩索計算

Fig. 2 實(shí)例：尺規(guī)計算機(jī)

1.1 定義算法

??計算，就是借助某種工具，遵照一定規(guī)則，以明確而機(jī)械的形式進(jìn)行。計算模型（計算機(jī)）就是計算中使用的工具。
??算法，即在特定計算模型下，旨在解決特定問題的指令序列。

特點(diǎn)：

①輸入、輸出明確
②正確性（可解決問題）
③確定性（任意算法都可描述為一個由基本操作注組成的序列）
④可行性（每一基本操作都可實(shí)現(xiàn)）
⑤有窮性（對于任何輸入，經(jīng)過有窮次計算后終止）

如何理解”有窮性“？

Fig. 3 Hailstone序列

例子:
$Hailstone(42) = \{42, 21, 64, 32, ..., 1 \rbrace$
Hailstone序列一定會呈現(xiàn)出整體下降的趨勢，盡管中間可能會飄忽不定。

#include<iostream>

int len_hailstone(int n){
    int length = 0;
    std::cout<<n<<", ";
    while(n>1){(n%2) ? n=n*3+1 : n/=2;std::cout<<n<<", "; length++;}
    std::cout<<std::endl;
    return length;
}

int main(int argc, char* argv[]){
    auto n = atoi(argv[1]);
    std::cout<<"length of hailstone("<<n<<"): "<<len_hailstone(n)<<std::endl;
    return 0;
}

?  Chapter1 ./hailstone 27     
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 
length of hailstone{27}: 111

問題：對于任意n，序列的長度是否是有窮的？
答案：不確定。這個序列的長度未必是有限的。因此上面的程序未必可以稱為一個“算法”。

什么是好算法
??對算法來說最重要的特征：效率
$Algorithms + Data Structures (DSA) = Programs$

1.2 計算模型

??如何評價不同DSA的效率: 度量。 ( If you cannot measure it, you can not improve it. )

測度：

Fig. 5 用某個實(shí)例的計算成本來評價DSA的效率是不現(xiàn)實(shí)的
分析：問題實(shí)例的規(guī)模，往往是決定計算成本的主要因素（正相關(guān)）
最壞情況分析原則：對于規(guī)模為n的所有實(shí)例中，只關(guān)注最壞（成本最高）者

1.2.1 圖靈機(jī)模型

Fig. 6 圖靈機(jī)概念

實(shí)例：通過圖靈機(jī)完成非負(fù)整數(shù)加一的功能。

Fig. 7

1.2.2 RAM模型

Fig. 8. RAM模型及其指令集

重點(diǎn)：這些模型將算法的運(yùn)行時間轉(zhuǎn)換為基本操作的次數(shù)來評價，從而將DSA的評價和單次實(shí)驗(yàn)的各種環(huán)境因素分離開。具體來說，每個算法的流程應(yīng)該是清晰、可羅列，且沒有歧義的。這就為評價算法提供了基礎(chǔ)。

二、復(fù)雜度分析

2.1 大 $O$ 記號

??大 $O$ 記號可以看做評價DSA的一把直尺，其刻度并不精細(xì)，而是主要用于評價DSA的“潛力”，比如它在求解大規(guī)模問題時的性能。更確切的說，大 $O$ 記號關(guān)注的是隨著n的增長(n>>2)，算法成本的增長趨勢。

Fig. 9. 大O記號

??大 $O$ 記號的處理手法:

常系數(shù)可忽略
低次項(xiàng)可忽略

2.1.1 常數(shù)復(fù)雜度 $O(1)$

?? $2 = 2013 = 2013^{2013} = O(1)$ 。這類算法的效率最高。

2.1.2 對數(shù)復(fù)雜度 $O(log^n)$

常底數(shù)和常數(shù)次冪無所謂：
??① $log_a^n = log_a^b * log_b^n = O(log^n)$
??② ${logn}^c = c*log^n = O(log^n)$

這類算法無限接近于 $O(1 )$ ，非常令人滿意。

2.1.3 多項(xiàng)式復(fù)雜度 $O(n^c)$

??多項(xiàng)式的最高此項(xiàng)即為復(fù)雜度 $O(n^k)$

線性復(fù)雜度: $O(n)$ ：代表線性函數(shù)。很多編程題復(fù)雜度都介乎 $O(n)-O(n^2)$ 。

2.1.4 指數(shù)復(fù)雜度 $O(2^n)$

??這類算法的計算成本增長的極快，通常認(rèn)為是不可忍受的。
?? $對任意c > 1, n^c = O(2^n)$ $http://證明: e^n = 1 + n + n^2/2! + n^3/3!$
?? $n^{1000}=O(1.0000001^n) = O(2^n)$

Fig. 10. 從多項(xiàng)式復(fù)雜度到指數(shù)復(fù)雜度

2.2 實(shí)例: Subset

Fig. 11 實(shí)例：Subset問題

這個問題如果沒有其他約束條件，最優(yōu)的算法就是逐一枚舉所有可能的子集，再統(tǒng)計其中元素的和。其復(fù)雜度為 $2^n$
Subset問題是一個NP-complete問題。

三、算法分析

??兩個主要任務(wù): 正確性 + 復(fù)雜度。

Fig. 12 算法分析：前提與方法

3.1 級數(shù)

算數(shù)級數(shù): $T(n) = 1 + 2 + ... + n = O(n^2)$
冪方級數(shù): $1^k + 2^k + 3^k + ... + n^k = O(n^{k+1})$ # 比冪次高一級
幾何級數(shù): $a^0 + a^1 + a^2 + ... + a^n = O(a^n)$
常用: $2^0 + 2^1 + 2^2 + ... + 2^n = O(2a^n)$
收斂級數(shù)
其他常見級數(shù):
①調(diào)和級數(shù) $h(n) = 1 + 1/2 + ... + 1/n = O(logn)$
②對數(shù)級數(shù): $log 1 + log2 + ... + logn = O(nlogn)$

3.1 循環(huán) vs. 級數(shù)

二重循環(huán)：
①兩個控制變量之間沒有耦合: 復(fù)雜度為 $O(n^2)$

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        O(1)_Operation(i, j)

②兩個控制變量之間存在耦合: 復(fù)雜度也是 $O(n^2)$

for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        O(1)_Operation(i, j)

Fig. 13 二重循環(huán)復(fù)雜度

③注意下面的循環(huán)復(fù)雜度為

for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j+=j)
        O(1)_Operation(i, j)

3.2 實(shí)例：非極端排序

問題：給定整數(shù)子集S，|S| = n>=3，找出元素a，確保a既不是S的最大值也不是最小值。
解：只需要從S中任取三個元素，然后找出這三個元素中的非極端元素即可。
說明: 某些情況下無論問題的規(guī)模多大，算法需要執(zhí)行的時間不變：

Fig. 14 非極端排序復(fù)雜度

3.3 實(shí)例：冒泡排序

Fig. 15 冒泡排序

vector<int> bubble_naive(vector<int> vec){
    int steps=0;
    int n = vec.size();
    for (int i=0; i<n; ++i){
            // No out of range error will be reported in cpp.
            for (int j=0; j<n-1; ++j){
                if (vec[j] > vec[j+1]){
                    swap(vec[j], vec[j+1]);
                }
                ++steps;
            }

        }
    cout<< "Steps: "<<steps<<endl;
    return vec;
}

vector<int> bubble_optimized(vector<int> vec){
    int steps=0;
    int n = vec.size();
    for (int i=n; i>0; --i){
            for (int j=0; j<i-1; ++j){
                if (vec[j] > vec[j+1]){
                    swap(vec[j], vec[j+1]);
                }
                ++steps;
            }
        }
    cout<< "Steps: "<<steps<<endl;
    return vec;
}

vector<int> bubble_optimized2(vector<int> vec){
    int steps=0;
    int n = vec.size();
    for (int i=n; i>0; --i){
        bool swapped = false;
        for (int j=0; j<i-1; ++j){
            if (vec[j] > vec[j+1]){
                swap(vec[j], vec[j+1]);
                swapped = true;
            }
            ++steps;
        }
        if (!swapped){
            cout<< "Break! Steps: "<<steps<<endl;
            return vec;
        }

    }
    cout<< "Steps: "<<steps<<endl;
    return vec;
}
// =======================

void main(){
    //vector<int> vec = {1,4,2,3,5,8,9,7,0};
    vector<int> vec = {1,2,4,3,5,6,7,8,9,22,0,11,12,3};
    print(vec);
    cout<<endl;
    auto vec1=bubble_naive(vec);
    auto vec2=bubble_optimized(vec);
    auto vec3=bubble_optimized2(vec);
    print(vec1);
    print(vec2);
    print(vec3);
}

Output:

Steps: 182
Steps: 91
Break! Steps: 88
0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 11, 12, 22,
0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 11, 12, 22,
0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 11, 12, 22,

四、迭代與遞推

4.1 減而治之

??所謂“減而治之”，就是講一個復(fù)雜的問題劃分成兩部分，其中一部分是

Fig. 16 減而治之

4.2 Max2問題

Fig. 16 迭代解法一

迭代解法二：初始化兩個指針（下標(biāo)索引）并確定其順序。從第三個元素開始掃描，每次掃描先將當(dāng)前下標(biāo)元素和x2位置數(shù)值（較小的元素）進(jìn)行比較，若大于x2，則x2的下標(biāo)更新為當(dāng)前下標(biāo)，同時和x1進(jìn)行比較。

Fig. 17. 迭代解法二
迭代解法二的最好情況需要n-1次比較；最壞情況需要2n-3次比較，并沒有實(shí)質(zhì)性的改善。
這個算法體現(xiàn)出分而治之思想的優(yōu)點(diǎn)。下面使用二分法，每次將數(shù)組均分成兩段，分別找出第一段(L)的max2元素X1L, X2L和第二段(R)的max2元素X1R, X2R，然后操作為：將X1L于X1R進(jìn)行比較確定全局最大值（如X1L > X1R），那么再將X2L和X1R進(jìn)行比較確定次大值。

Fig. 18 二分遞歸

#include<iostream>
#include<vector>
using namespace std;

//vector A: [lo, lo+1, lo+2, ..., hi)
void max2(vector<int> A, int lo, int hi, int &x1, int& x2){
    if (hi - lo == 3) {
        if (A[lo] < A[lo+1]){
            if (A[lo+1]<A[lo+2]) {
                x1=lo+2;
                x2=A[lo+1]>A[lo]?lo+1:lo;
            } else {
                x1=lo+1;
                x2=A[lo+2]>A[lo]?lo+2:lo;};
        }
        else { // lo > lo+1
            if (A[lo]>A[lo+2]) {
                x1=lo;
                x2=A[lo+1]>A[lo+2] ? lo+1:lo+2;
            } else {
                x1=lo+2;x2=A[lo+1]>A[lo]?lo+1:lo;
            }
        }
        return;
    }  //T(3)<=3;

    if (hi - lo == 2) {
        if (A[lo]>A[hi-1]){
            x1 = lo;
            x2 = hi-1;
        } else {
            x1 = hi-1;
            x2 = lo;
        }
        return;
    }
    int mi = (lo + hi) / 2;
    int X1L, X2L; max2(A, lo, mi, X1L, X2L);
    int X1R, X2R; max2(A, mi, hi, X1R, X2R);
    if (A[X1L] > A[X1R]){
        x1 = X1L;
        x2 = A[X2L] > A[X1R] ? X2L : X1R;
    }
    else{
        x1 = X1R;
        x2 = A[X2R] > A[X1L] ? X2R : X1L;
    }
}

int main(){
    vector<int> A={1,3,4,0,9,-2,8,11};
    //vector<int> A={5,6};
    int lo = 0;
    int hi = A.size();
    int x1, x2;
    max2(A, lo, hi, x1, x2);
    cout<<"Max 2 number: "<< A[x1]<<", "<<A[x2]<<endl;
}

龍哥系統(tǒng)組常用面試題目：

連續(xù)子數(shù)組的和（動態(tài)規(guī)劃）
二維數(shù)組向右或者向下走，選擇和最大的路徑（動態(tài)規(guī)劃）
立方體八個頂點(diǎn)，一個點(diǎn)給一個數(shù)，問能否實(shí)現(xiàn)每個面四個頂點(diǎn)和相等 (動態(tài)規(guī)劃/全排列，了解下)
求一個數(shù)組中最大的K個數(shù) （堆排序 /c++ map 平衡二叉樹）
背包問題
長度為n-1的數(shù)組中存放了1-n之間的n-1個數(shù)。找到缺失的數(shù)
二維數(shù)組從左往右從上往下遞增，判斷給定的數(shù)是否在數(shù)組中，若在則返回位置（時間復(fù)雜度要求M+N）
找出鏈表中環(huán)的位置/鏈表的刪除和插入
字符串處理: 將字符串中的某個字符替換為指定字符串（不含目標(biāo)字符）

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記——第一章：緒論（上）

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記——第一章：緒論（上）

一、目標(biāo)：計算

1.1 定義算法

1.2 計算模型

1.2.1 圖靈機(jī)模型

1.2.2 RAM模型

二、復(fù)雜度分析

2.1 大 $O$ 記號

2.1.1 常數(shù)復(fù)雜度 $O(1)$

2.1.2 對數(shù)復(fù)雜度 $O(log^n)$

2.1.3 多項(xiàng)式復(fù)雜度 $O(n^c)$

2.1.4 指數(shù)復(fù)雜度 $O(2^n)$

2.2 實(shí)例: Subset

三、算法分析

3.1 級數(shù)

3.1 循環(huán) vs. 級數(shù)

3.2 實(shí)例：非極端排序

3.3 實(shí)例：冒泡排序

四、迭代與遞推

4.1 減而治之

4.2 Max2問題

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記——第一章：緒論（上）

一、目標(biāo)：計算

1.1 定義算法

1.2 計算模型

1.2.1 圖靈機(jī)模型

1.2.2 RAM模型

二、復(fù)雜度分析

2.1 大記號

2.1.1 常數(shù)復(fù)雜度

2.1.2 對數(shù)復(fù)雜度

2.1.3 多項(xiàng)式復(fù)雜度

2.1.4 指數(shù)復(fù)雜度

2.2 實(shí)例: Subset

三、算法分析

3.1 級數(shù)

3.1 循環(huán) vs. 級數(shù)

3.2 實(shí)例：非極端排序

3.3 實(shí)例：冒泡排序

四、迭代與遞推

4.1 減而治之

4.2 Max2問題

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

二、復(fù)雜度分析

2.1 大 $O$ 記號

2.1.1 常數(shù)復(fù)雜度 $O(1)$

2.1.2 對數(shù)復(fù)雜度 $O(log^n)$

2.1.3 多項(xiàng)式復(fù)雜度 $O(n^c)$

2.1.4 指數(shù)復(fù)雜度 $O(2^n)$

三、算法分析

四、迭代與遞推