?1 數(shù)據(jù)結(jié)構(gòu)與算法是什么颤殴？
看了一篇文章觅廓，感覺(jué)文章給出的比喻非常貼切。比如一場(chǎng)戰(zhàn)爭(zhēng)中涵但，碼農(nóng)可以比作是戰(zhàn)場(chǎng)上的將軍杈绸，用的代碼比作是小兵，那么數(shù)據(jù)結(jié)構(gòu)與算法就是兵法０痢ＭА！
我們可以不看兵法在戰(zhàn)場(chǎng)上肉搏澈侠，如此劫侧，可能會(huì)勝利，可能會(huì)失敗哨啃。即使勝利烧栋，可能也會(huì)付出巨大的代價(jià)。我們寫程序亦然：沒(méi)有看過(guò)數(shù)據(jù)結(jié)構(gòu)和算法棘催，有時(shí)面對(duì)問(wèn)題可能會(huì)沒(méi)有任何思路劲弦，不知如何下手去解決耳标；大部分時(shí)間可能解決了問(wèn)題醇坝，可是對(duì)程序運(yùn)行的效率和開銷沒(méi)有意識(shí)，性能低下；有時(shí)會(huì)借助別人開發(fā)的利器暫時(shí)解決了問(wèn)題呼猪，可是遇到性能瓶頸的時(shí)候画畅，又不知該如何進(jìn)行針對(duì)性的優(yōu)化。因此宋距，數(shù)據(jù)結(jié)構(gòu)與算法轴踱，就是要讓我們做到胸有成竹，掌握兵法谚赎，游刃有余地開展程序地編寫淫僻，高效地實(shí)現(xiàn)代碼運(yùn)作！
所有代碼是基于python3編寫的壶唤。
2 數(shù)據(jù)結(jié)構(gòu)與算法的研究問(wèn)題雳灵？
2-1 引入
如果 a+b+c=1000，且 a^2+b^2=c^2（a,b,c 為自然數(shù)）闸盔，如何求出所有a悯辙、b、c可能的組合?
解法1：遍歷所有
因此我們可以看到迎吵，當(dāng)算法以純遍歷的形式開展求解時(shí)躲撰，時(shí)間運(yùn)行非常長(zhǎng)。
解法2：少去一個(gè)循環(huán)
可以看到击费，少了一個(gè)for循環(huán)拢蛋，可以在一定程度上降低程序運(yùn)行的時(shí)間。另外蔫巩，我們都聽(tīng)說(shuō)過(guò)內(nèi)存這件事瓤狐，因此我們往往希望能夠在程序運(yùn)行時(shí)緩存更少的數(shù)據(jù)空間，節(jié)約空間以便開展其它的并行任務(wù)批幌！
總的來(lái)說(shuō)础锐，兩個(gè)名詞，時(shí)間復(fù)雜度與空間復(fù)雜度荧缘，就是我們所要研究的問(wèn)題皆警。
因此，數(shù)據(jù)結(jié)構(gòu)與算法的五大特征先總結(jié)一下：
（1）輸入截粗，輸入為0個(gè)以上信姓；（2）輸出，輸出為1個(gè)以上绸罗；（3）有窮性意推，不能無(wú)限制的計(jì)算~；（4）確定性珊蟀，不能輸出有歧義的解菊值；（5）可行性：算法編寫的算法可以行的通的。
2-2??衡量算法的效率：
在2-1中，我們嘗試了運(yùn)用兩種求解方法腻窒，最后運(yùn)用一個(gè)時(shí)間來(lái)對(duì)比了我們的算法昵宇。但是需要指出的是，假設(shè)把解法1放在一個(gè)超級(jí)計(jì)算機(jī)上（比如天河號(hào)儿子，亂猜的）所運(yùn)行的時(shí)間可能要比解法2放在一個(gè)破筆記本電腦上的時(shí)間要短瓦哎。那此時(shí)我們說(shuō)解法1要比解法2高效，你覺(jué)得這樣合理么柔逼？? ?顯然蒋譬，答案是否定的。? ?因此單靠時(shí)間來(lái)衡量算法的優(yōu)劣顯然是行不通的Ｓ涫省羡铲！！? ?也就是說(shuō)一個(gè)算法的求解是離不開計(jì)算機(jī)環(huán)境的硬件配置資源的儡毕。
（1）時(shí)間復(fù)雜度也切。以2-1中的解法1為例，a腰湾，b雷恃，c要分別遍歷1001次，那么此時(shí)遍歷完整個(gè)可能性解费坊，是不是要 1001x1001x1001 次倒槐，這么多計(jì)算!? 而解法2的話，對(duì)于for循環(huán)只需要遍歷1001*1001次循環(huán)附井√衷剑可見(jiàn)兩者足足差了約1001倍。
? ? ? ? ?因此我們以這種類似于循環(huán)次數(shù)作為研究對(duì)象永毅，即假定程序每執(zhí)行一次操作是一個(gè)時(shí)間單位把跨，那么有多少次操作就代表其會(huì)花掉多少時(shí)間。對(duì)于算法的時(shí)間效率沼死，我們可以用“大O記法”來(lái)表示着逐。“大O記法”：對(duì)于單調(diào)的整數(shù)函數(shù)f，如果存在一個(gè)整數(shù)函數(shù)g和實(shí)常數(shù)c>0意蛀，使得對(duì)于充分大的n總有f(n)<=c*g(n)耸别，就說(shuō)函數(shù)g是f的一個(gè)漸近函數(shù)（忽略常數(shù)），記為f(n)=O(g(n))县钥。也就是說(shuō)秀姐，在趨向無(wú)窮的極限意義下，函數(shù)f的增長(zhǎng)速度受到函數(shù)g的約束若贮，亦即函數(shù)f與函數(shù)g的特征相似省有。時(shí)間復(fù)雜度：假設(shè)存在函數(shù)g痒留，使得算法A處理規(guī)模為n的問(wèn)題示例所用時(shí)間為T(n)=O(g(n))，則稱O(g(n))為算法A的漸近時(shí)間復(fù)雜度锥咸，簡(jiǎn)稱時(shí)間復(fù)雜度，記為T(n)细移。
? ???????對(duì)于算法進(jìn)行特別具體的細(xì)致分析雖然很好搏予，但在實(shí)踐中的實(shí)際價(jià)值有限。對(duì)于算法的時(shí)間性質(zhì)和空間性質(zhì)弧轧，最重要的是其數(shù)量級(jí)和趨勢(shì)雪侥，這些是分析算法效率的主要部分。而計(jì)量算法基本操作數(shù)量的規(guī)模函數(shù)中那些常量因子可以忽略不計(jì)精绎。例如速缨，可以認(rèn)為3n**2和100n**2屬于同一個(gè)量級(jí)，如果兩個(gè)算法處理同樣規(guī)模實(shí)例的代價(jià)分別為這兩個(gè)函數(shù)代乃，就認(rèn)為它們的效率“差不多”旬牲，都為n**2級(jí)。
（2）三個(gè)概念：? 對(duì)于它們的理解搁吓，等將各種排序方法學(xué)完原茅，就會(huì)有一個(gè)相對(duì)清晰地認(rèn)知了。
? ? ? ? ?最壞時(shí)間復(fù)雜度：算法完成工作最多需要花費(fèi)的基本操作堕仔；
? ? ? ? ?最優(yōu)時(shí)間復(fù)雜度：算法完成工作最少需要花費(fèi)的基本操作擂橘；
? ? ? ? ?平均時(shí)間復(fù)雜度：算法完成工作平均需要花費(fèi)的基本操作；
（3）時(shí)間復(fù)雜度的幾條基本規(guī)則：
? ? ? ? ?基本操作摩骨，即只有常數(shù)項(xiàng)通贞，認(rèn)為其時(shí)間復(fù)雜度為O(1)
????????順序結(jié)構(gòu)，時(shí)間復(fù)雜度按加法進(jìn)行計(jì)算
????????循環(huán)結(jié)構(gòu)恼五，時(shí)間復(fù)雜度按乘法進(jìn)行計(jì)算
????????分支結(jié)構(gòu)昌罩，時(shí)間復(fù)雜度取最大值
????????判斷一個(gè)算法的效率時(shí)，往往只需要關(guān)注操作數(shù)量的最高次項(xiàng)灾馒，其它次要項(xiàng)和常數(shù)項(xiàng)可以忽略
????????在沒(méi)有特殊說(shuō)明時(shí)峡迷，我們所分析的算法的時(shí)間復(fù)雜度都是指最壞時(shí)間復(fù)雜度。 因此解法1的時(shí)間復(fù)雜度要比解法2 的時(shí)間復(fù)雜度大你虹。
2-3 常見(jiàn)的時(shí)間復(fù)雜度
3 其它
python中會(huì)用到list列表绘搞，list應(yīng)該是一個(gè)順序表，因此其時(shí)間復(fù)雜度如下：
? ? 字典的復(fù)雜度
例子：實(shí)際上當(dāng)我們?cè)谒伎歼@個(gè)問(wèn)題的時(shí)候傅物，我們已經(jīng)用到了數(shù)據(jù)結(jié)構(gòu)夯辖。列表和字典都可以存儲(chǔ)一個(gè)班的學(xué)生信息，但是想要在列表中獲取一名同學(xué)的信息時(shí)董饰，就要遍歷這個(gè)列表蒿褂，其時(shí)間復(fù)雜度為O(n)圆米，而使用字典存儲(chǔ)時(shí)，可將學(xué)生姓名作為字典的鍵啄栓，學(xué)生信息作為值娄帖，進(jìn)而查詢時(shí)不需要遍歷便可快速獲取到學(xué)生信息，其時(shí)間復(fù)雜度為O(1)昙楚。
因此回到我們的主題：數(shù)據(jù)結(jié)構(gòu)與算法
? ??????數(shù)據(jù)是一個(gè)抽象的概念近速，將其進(jìn)行分類后得到程序設(shè)計(jì)語(yǔ)言中的基本類型。如：int堪旧，float削葱，char等。數(shù)據(jù)元素之間不是獨(dú)立的淳梦，存在特定的關(guān)系析砸，這些關(guān)系便是結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的關(guān)系爆袍。
? ??????數(shù)據(jù)結(jié)構(gòu)只是靜態(tài)的描述了數(shù)據(jù)元素之間的關(guān)系首繁。
????????高效的程序需要在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上設(shè)計(jì)和選擇算法。
? ??????程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法
? ??????總結(jié)：算法是為了解決實(shí)際問(wèn)題而設(shè)計(jì)的陨囊，數(shù)據(jù)結(jié)構(gòu)是算法需要處理的問(wèn)題載體
? ? ? ? 常見(jiàn)的數(shù)據(jù)運(yùn)算有五種：
? ??????插入蛮瞄；刪除；修改谆扎；查找挂捅；排序
參考鏈接：https://www.bilibili.com/video/av21540971?p=39??
