數(shù)據(jù)結構和算法開篇

如果說,熟練掌握編程語言是外功展哭,那么數(shù)據(jù)結構可謂是內(nèi)功心法了

以下是我學習數(shù)據(jù)結構的總結和一些筆記

數(shù)據(jù)結構(Data Structure)

  • 抽象數(shù)據(jù)類型(ADT)的物理實現(xiàn)
  • “數(shù)據(jù)結構”是計算機中存儲秽之,組織數(shù)據(jù)的方式神年。
  • “數(shù)據(jù)結構是數(shù)據(jù)對象”以及存在于該對象的實例和組成實例的數(shù)據(jù)元素之間的各種聯(lián)系
  • 解決問題方法的效率跟數(shù)據(jù)的組織方式帘靡、空間的利用效率算法的巧妙程度有關

例子1:

void PrintN( int N )
{
    int i;
    for( i=1 ; i<N ; i++)
    printf("%d\n",i);
    return;
}
void PrintN( int N )
{
    if( N )
    {
        PrintN(N-1);
        printf("%d\n",N);
    } 
    return;
}

這個程序前一個用了循環(huán)實現(xiàn)打印1-N玄货,后面一個采用遞歸的方法實現(xiàn)的皇钞,很明顯遞歸的效率很低,是因為松捉,遞歸實現(xiàn)原理是以堆棧的方式夹界,也就是說函數(shù)把 PrintN(N) 到PrintN(1)這N個函數(shù)壓入棧中,在依次打印出來隘世,內(nèi)存消耗巨大可柿。
圖示:

內(nèi)存圖

例子2:

計算

多項式相加

double f(int n , double a[], double x)
{
    int i;
    double p = a[0];
    for( i=1 ; i<=n ; i++)
        p+= ( a[i] * pow( x , i ));
    return p;
}
double f(int n , double a[], double x)
{
    int i;
    double p = a[0];
    for( i=n ; i>0 ; i--)
        p= a[i-1] +x*p;
    return p;
}

在計算機中,有多次乘法與加法的運算時丙者,一般按照權重复斥,只需比較乘法次數(shù)就可以了,第一個算法每一次循環(huán)執(zhí)行了i+1次乘法蔓钟,一共執(zhí)行了(N^2+3*N)/2次永票,第二種算法執(zhí)行了N次乘法卵贱,顯然第二種效率高滥沫,這就是算法的妙用

其實數(shù)據(jù)結構是由一些基本數(shù)據(jù)類型組合成了一個復雜的數(shù)據(jù)類型侣集,用于解決某一類問題(基本問題有數(shù)據(jù)的增加,刪除兰绣,條件查詢世分,遍歷等)

總結:到底什么是數(shù)據(jù)結構?

  • 數(shù)據(jù)對象在計算機中的組織方式

    1. 邏輯結構
    2. 物理存儲結構
  • 數(shù)據(jù)對象必定與一系列加在其上的操作相關聯(lián)

  • 完成這些操作所用的方法就是算法

抽象數(shù)據(jù)類型(Abstract Data Type)

  • 數(shù)據(jù)類型
    1. 數(shù)據(jù)對象集
    2. 數(shù)據(jù)集合相關聯(lián)的操作集
  • 抽象:描述數(shù)據(jù)類型的方法不依賴于具體實現(xiàn)
    1. 與存放的機器無關
    2. 與數(shù)據(jù)存儲的物理結構無關
    3. 與實現(xiàn)操作的算法和編程語言無關

算法

什么是算法缀辩?

  • 一個有限指令集
  • 接受一些輸入(有些時候不需要輸入)
  • 產(chǎn)生輸出
  • 一定在有限步驟之后終止
  • 每一條指令必須

時間復雜度Tn

根據(jù)算法寫成的程序在執(zhí)行時占用存儲單源的長度

空間復雜度Sn

根據(jù)算法寫成的程序在執(zhí)行時好費時間的長度

牛刀小試

用算法實現(xiàn) 求一個數(shù)列的最大子列和

題目一

給出下列四個算法:

//第一種算法:時間復雜度為 T(n^3)
int MaxSubseqSum1(int a[] , int N)
{
    int thisSum=0 , MaxSum=0;
        int i,j,k;
    for( i=0 ; i<N ; i++ )  /* i 是子列左端位置 */ 
        for( int j=i ; j<N ; j++ )   /* j是子列右端位置 */
        {   
            thisSum = 0;   /* thisSum 是從 a[i] 到 a[j] 的子列和 */
            for(int k=i;k<j;k++)thisSum+=a[k];
            /* 如果剛得到的這個子列和更大臭埋,則更新結果 */
            if(thisSum>MaxSum) MaxSum = thisSum;
        }
    return MaxSum;
} 
image.png
image.png
//最快的算法,時間復雜度為T(n)
int MaxSubseqSum1(int a[] , int N)
{
    int thisSum=0 , MaxSum = 0;
        int i;
    for( i=0 ; i<N ; i++)
    {
        thisSum+=a[i];     /* 向右累加 */
        /* 發(fā)現(xiàn)更大的則更新當前結果 */
        if(thisSum>MaxSum)MaxSum = thisSum;
       /* 如果當前子列和為負數(shù)臀玄,則不可能是后面的部分和增大瓢阴,故舍棄 */
        else if(thisSum<0)thisSum=0;
    }
    return MaxSum;
}

算法三可以嘗試寫一下。
以上資料來源于 MOOC 《數(shù)據(jù)結構》

最后編輯于
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末健无,一起剝皮案震驚了整個濱河市荣恐,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌累贤,老刑警劉巖叠穆,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異臼膏,居然都是意外死亡硼被,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進店門渗磅,熙熙樓的掌柜王于貴愁眉苦臉地迎上來嚷硫,“玉大人,你說我怎么就攤上這事始鱼÷畚。” “怎么了?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵风响,是天一觀的道長嘉汰。 經(jīng)常有香客問我,道長状勤,這世上最難降的妖魔是什么鞋怀? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮持搜,結果婚禮上密似,老公的妹妹穿的比我還像新娘。我一直安慰自己葫盼,他們只是感情好残腌,可當我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著,像睡著了一般抛猫。 火紅的嫁衣襯著肌膚如雪蟆盹。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天闺金,我揣著相機與錄音逾滥,去河邊找鬼。 笑死败匹,一個胖子當著我的面吹牛寨昙,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播掀亩,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼舔哪,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了槽棍?” 一聲冷哼從身側(cè)響起尸红,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎刹泄,沒想到半個月后外里,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡特石,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年盅蝗,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片姆蘸。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡墩莫,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出逞敷,到底是詐尸還是另有隱情狂秦,我是刑警寧澤,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布推捐,位于F島的核電站裂问,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏牛柒。R本人自食惡果不足惜堪簿,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望皮壁。 院中可真熱鬧椭更,春花似錦、人聲如沸蛾魄。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至舌狗,卻和暖如春叽奥,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背把夸。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留铭污,地道東北人恋日。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像嘹狞,于是被迫代替她去往敵國和親岂膳。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容