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

一弦追、目標(biāo):計(jì)算

??整個(gè)計(jì)算機(jī)科學(xué)的目的劲件,都是為了實(shí)現(xiàn)高效和低耗的計(jì)算。為了理解什么是計(jì)算牵辣,我們首先來(lái)看幾個(gè)實(shí)例躺枕。


Fig. 1 實(shí)例:繩索計(jì)算
Fig. 2 實(shí)例:尺規(guī)計(jì)算機(jī)
1.1 定義算法

??計(jì)算服猪,就是借助某種工具供填,遵照一定規(guī)則拐云,以明確而機(jī)械的形式進(jìn)行罢猪。計(jì)算模型(計(jì)算機(jī))就是計(jì)算中使用的工具。
??算法叉瘩,即在特定計(jì)算模型下膳帕,旨在解決特定問(wèn)題的指令序列。

  • 特點(diǎn):

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


  • 如何理解”有窮性“?
    Fig. 3 Hailstone序列

    例子:
    Hailstone(42) = \{42, 21, 64, 32, ..., 1 \rbrace
    Hailstone序列一定會(huì)呈現(xiàn)出整體下降的趨勢(shì),盡管中間可能會(huì)飄忽不定。
#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
  • 問(wèn)題:對(duì)于任意n, 序列的長(zhǎng)度是否是有窮的?
  • 答案:不確定。這個(gè)序列的長(zhǎng)度未必是有限的。因此上面的程序未必可以稱(chēng)為一個(gè)“算法”坟募。

  • 什么是好算法
    ??對(duì)算法來(lái)說(shuō)最重要的特征:效率
    Algorithms + Data Structures (DSA) = Programs
1.2 計(jì)算模型

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

  • 測(cè)度:


    Fig. 5 用某個(gè)實(shí)例的計(jì)算成本來(lái)評(píng)價(jià)DSA的效率是不現(xiàn)實(shí)的
  • 分析:?jiǎn)栴}實(shí)例的規(guī)模围详,往往是決定計(jì)算成本的主要因素(正相關(guān))
  • 最壞情況分析原則:對(duì)于規(guī)模為n的所有實(shí)例中雹食,只關(guān)注最壞(成本最高)者
1.2.1 圖靈機(jī)模型
Fig. 6 圖靈機(jī)概念
  • 實(shí)例:通過(guò)圖靈機(jī)完成非負(fù)整數(shù)加一的功能埠通。


    Fig. 7
1.2.2 RAM模型
Fig. 8. RAM模型及其指令集
  • 重點(diǎn):這些模型將算法的運(yùn)行時(shí)間轉(zhuǎn)換為基本操作的次數(shù)來(lái)評(píng)價(jià)众雷,從而將DSA的評(píng)價(jià)和單次實(shí)驗(yàn)的各種環(huán)境因素分離開(kāi)。具體來(lái)說(shuō)悯嗓,每個(gè)算法的流程應(yīng)該是清晰临梗、可羅列红淡,且沒(méi)有歧義的遂黍。這就為評(píng)價(jià)算法提供了基礎(chǔ)。

二带到、復(fù)雜度分析

2.1 大O記號(hào)

??大O記號(hào)可以看做評(píng)價(jià)DSA的一把直尺闪金,其刻度并不精細(xì)损俭,而是主要用于評(píng)價(jià)DSA的“潛力”,比如它在求解大規(guī)模問(wèn)題時(shí)的性能鼻听。更確切的說(shuō),大O記號(hào)關(guān)注的是隨著n的增長(zhǎng)(n>>2),算法成本的增長(zhǎng)趨勢(shì)。

Fig. 9. 大O記號(hào)

??大O記號(hào)的處理手法:

  1. 常系數(shù)可忽略
  2. 低次項(xiàng)可忽略
2.1.1 常數(shù)復(fù)雜度O(1)

?? 2 = 2013 = 2013^{2013} = O(1)。這類(lèi)算法的效率最高返弹。

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

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

  • 這類(lèi)算法無(wú)限接近于O(1 )丐巫,非常令人滿(mǎn)意祝闻。
2.1.3 多項(xiàng)式復(fù)雜度 O(n^c)

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

  • 線(xiàn)性復(fù)雜度: O(n): 代表線(xiàn)性函數(shù)堤框。很多編程題復(fù)雜度都介乎O(n)-O(n^2)委可。
2.1.4 指數(shù)復(fù)雜度 O(2^n)

??這類(lèi)算法的計(jì)算成本增長(zhǎng)的極快崇决,通常認(rèn)為是不可忍受的塔嬉。
??對(duì)任意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問(wèn)題
  • 這個(gè)問(wèn)題如果沒(méi)有其他約束條件玩徊,最優(yōu)的算法就是逐一枚舉所有可能的子集,再統(tǒng)計(jì)其中元素的和谨究。其復(fù)雜度為2^n
  • Subset問(wèn)題是一個(gè)NP-complete問(wèn)題恩袱。

三、算法分析

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


Fig. 12 算法分析:前提與方法
3.1 級(jí)數(shù)
  • 算數(shù)級(jí)數(shù): T(n) = 1 + 2 + ... + n = O(n^2)
  • 冪方級(jí)數(shù): 1^k + 2^k + 3^k + ... + n^k = O(n^{k+1}) # 比冪次高一級(jí)
  • 幾何級(jí)數(shù): a^0 + a^1 + a^2 + ... + a^n = O(a^n)
    常用: 2^0 + 2^1 + 2^2 + ... + 2^n = O(2a^n)
  • 收斂級(jí)數(shù)
  • 其他常見(jiàn)級(jí)數(shù):
    ①調(diào)和級(jí)數(shù) h(n) = 1 + 1/2 + ... + 1/n = O(logn)
    ②對(duì)數(shù)級(jí)數(shù): log 1 + log2 + ... + logn = O(nlogn)
3.1 循環(huán) vs. 級(jí)數(shù)
  • 二重循環(huán):
    ①兩個(gè)控制變量之間沒(méi)有耦合: 復(fù)雜度為O(n^2)
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        O(1)_Operation(i, j)  

②兩個(gè)控制變量之間存在耦合: 復(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í)例:非極端排序
  • 問(wèn)題:給定整數(shù)子集S畔塔,|S| = n>=3,找出元素a,確保a既不是S的最大值也不是最小值澈吨。
  • 解:只需要從S中任取三個(gè)元素把敢,然后找出這三個(gè)元素中的非極端元素即可。
  • 說(shuō)明: 某些情況下無(wú)論問(wèn)題的規(guī)模多大谅辣,算法需要執(zhí)行的時(shí)間不變:


    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 減而治之

??所謂“減而治之”,就是講一個(gè)復(fù)雜的問(wèn)題劃分成兩部分桑阶,其中一部分是

Fig. 16 減而治之
4.2 Max2問(wèn)題
Fig. 16 迭代解法一
  • 迭代解法二:初始化兩個(gè)指針(下標(biāo)索引)并確定其順序柏副。從第三個(gè)元素開(kāi)始掃描,每次掃描先將當(dāng)前下標(biāo)元素和x2位置數(shù)值(較小的元素)進(jìn)行比較联逻,若大于x2搓扯,則x2的下標(biāo)更新為當(dāng)前下標(biāo),同時(shí)和x1進(jìn)行比較包归。


    Fig. 17. 迭代解法二
  • 迭代解法二的最好情況需要n-1次比較锨推;最壞情況需要2n-3次比較,并沒(méi)有實(shí)質(zhì)性的改善公壤。
  • 這個(gè)算法體現(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ù)組的和 (動(dòng)態(tài)規(guī)劃)
  • 二維數(shù)組向右或者向下走译荞,選擇和最大的路徑 (動(dòng)態(tài)規(guī)劃)
  • 立方體八個(gè)頂點(diǎn),一個(gè)點(diǎn)給一個(gè)數(shù)休弃,問(wèn)能否實(shí)現(xiàn)每個(gè)面四個(gè)頂點(diǎn)和相等 (動(dòng)態(tài)規(guī)劃/全排列吞歼,了解下)
  • 求一個(gè)數(shù)組中最大的K個(gè)數(shù) (堆排序 /c++ map 平衡二叉樹(shù))
  • 背包問(wèn)題
  • 長(zhǎng)度為n-1的數(shù)組中存放了1-n之間的n-1個(gè)數(shù)。找到缺失的數(shù)
  • 二維數(shù)組從左往右從上往下遞增塔猾,判斷給定的數(shù)是否在數(shù)組中篙骡,若在則返回位置 (時(shí)間復(fù)雜度要求M+N)
  • 找出鏈表中環(huán)的位置/鏈表的刪除和插入
  • 字符串處理: 將字符串中的某個(gè)字符替換為指定字符串(不含目標(biāo)字符)
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市丈甸,隨后出現(xiàn)的幾起案子糯俗,更是在濱河造成了極大的恐慌,老刑警劉巖睦擂,帶你破解...
    沈念sama閱讀 222,590評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件得湘,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡祈匙,警方通過(guò)查閱死者的電腦和手機(jī)忽刽,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,157評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén)天揖,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人跪帝,你說(shuō)我怎么就攤上這事今膊。” “怎么了伞剑?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,301評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵斑唬,是天一觀(guān)的道長(zhǎng)。 經(jīng)常有香客問(wèn)我黎泣,道長(zhǎng)恕刘,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,078評(píng)論 1 300
  • 正文 為了忘掉前任抒倚,我火速辦了婚禮褐着,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘托呕。我一直安慰自己含蓉,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,082評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布项郊。 她就那樣靜靜地躺著馅扣,像睡著了一般。 火紅的嫁衣襯著肌膚如雪着降。 梳的紋絲不亂的頭發(fā)上差油,一...
    開(kāi)封第一講書(shū)人閱讀 52,682評(píng)論 1 312
  • 那天,我揣著相機(jī)與錄音任洞,去河邊找鬼蓄喇。 笑死,一個(gè)胖子當(dāng)著我的面吹牛交掏,可吹牛的內(nèi)容都是我干的公罕。 我是一名探鬼主播,決...
    沈念sama閱讀 41,155評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼耀销,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了铲汪?” 一聲冷哼從身側(cè)響起熊尉,我...
    開(kāi)封第一講書(shū)人閱讀 40,098評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎掌腰,沒(méi)想到半個(gè)月后狰住,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,638評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡齿梁,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,701評(píng)論 3 342
  • 正文 我和宋清朗相戀三年催植,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了肮蛹。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,852評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡创南,死狀恐怖伦忠,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情稿辙,我是刑警寧澤昆码,帶...
    沈念sama閱讀 36,520評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站邻储,受9級(jí)特大地震影響赋咽,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜吨娜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,181評(píng)論 3 335
  • 文/蒙蒙 一脓匿、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧宦赠,春花似錦陪毡、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,674評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至尺借,卻和暖如春绊起,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背燎斩。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,788評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工虱歪, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人栅表。 一個(gè)月前我還...
    沈念sama閱讀 49,279評(píng)論 3 379
  • 正文 我出身青樓笋鄙,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親怪瓶。 傳聞我的和親對(duì)象是個(gè)殘疾皇子萧落,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,851評(píng)論 2 361