什么是數(shù)據(jù)結(jié)構(gòu)阀蒂？
數(shù)據(jù)結(jié)構(gòu)是指一組數(shù)據(jù)的存儲結(jié)構(gòu)。
什么是算法弟蚀？
算法是操作一組數(shù)據(jù)的方法蚤霞。
10個常用的數(shù)據(jù)結(jié)構(gòu)
數(shù)組、鏈表粗梭、棧争便、隊列、散列表断医、二叉樹滞乙、堆奏纪、跳表、圖斩启、Trie樹
10個算法
遞歸序调、排序、二分查找兔簇、搜索发绢、哈希算法、貪心算法垄琐、分治算法边酒、回溯算法、動態(tài)規(guī)劃狸窘、字符串匹配算法
時間復(fù)雜度
大O時間復(fù)雜度表示法
所有代碼的執(zhí)行時間T(n)與每行代碼的執(zhí)行次數(shù)n成正比;
T(n) = O(f(n)
T(n)代表代碼的執(zhí)行時間墩朦；n表示數(shù)據(jù)規(guī)模；f(n)表示每行代碼執(zhí)行的次數(shù)總和翻擒；
O表示代碼的執(zhí)行時間T(n)與表達(dá)式f(n)成正比氓涣；
公式中的低階、常量陋气、系數(shù)都可以忽略劳吠；
大O時間復(fù)雜度（簡稱時間復(fù)雜度）
大O時間復(fù)雜度實際上并不是具體表示代碼真正的執(zhí)行時間，而是表示代碼的執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢巩趁，所以也叫漸進(jìn)時間復(fù)雜度痒玩。、
時間復(fù)雜度分析
* 只關(guān)注循環(huán)執(zhí)行次數(shù)最多的那段代碼晶渠；
* 加法法則：總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度凰荚；
* 乘法法則：嵌套代碼復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積；
幾種常見的時間復(fù)雜度分析
常量階：O(1)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 指數(shù)階：O(2n）#2的n次方
對數(shù)階：O(logn)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?階乘階：O(n!)
線性階：O(n)
線性對數(shù)階：O(nlogn)
平方階：O(n2)褒脯、立方階：O(n3）便瑟、k次方階：O(nk）
對于上面羅列的復(fù)雜度量級，可以粗略的分為兩類番川，多項式量級和非多項式量級到涂。非多項式量級只有兩個：指數(shù)階和階乘階；
把時間復(fù)雜度為多項式量級的算法問題叫做NP（Non-Deterministic Polyomial颁督，非確定多項式）問題践啄；
O(1)
只要代碼的執(zhí)行時間不隨著n的增大而增長，這樣的時間復(fù)雜度都計作O(1)沉御∮旆恚或者說：一般情況下，只要算法中不存在循環(huán)語句、遞歸語句伐谈，即使有成千上萬行的代碼烂完，其時間復(fù)雜度也是O(1)；
O(logn)诵棵、O(nlogn)
對數(shù)階時間復(fù)雜度非常常見抠蚣，同時也是最難分析的一種。如常用的歸并排序履澳、快速排序的時間復(fù)雜度都是O(nlogn)嘶窄；
空間復(fù)雜度分析
時間復(fù)雜度的全稱是漸進(jìn)時間復(fù)雜度，表示算法的執(zhí)行時間與數(shù)據(jù)規(guī)模之間的增長關(guān)系距贷；空間復(fù)雜度全稱就是漸進(jìn)空間復(fù)雜度柄冲，表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系；
我們常用的空間復(fù)雜度就是O(1)储耐、O(n)羊初、O(n2)，像O(logn)什湘、O(nlogn)這樣的對數(shù)階復(fù)雜度平時用不到；
淺析最好晦攒、最壞闽撤、平均、均攤時間復(fù)雜度
最好情況時間復(fù)雜度
在最理想的情況下脯颜，執(zhí)行這段代碼的時間復(fù)雜度哟旗；
最壞情況時間復(fù)雜度
在最糟糕的情況下，執(zhí)行這段代碼的時間復(fù)雜度栋操；
平均情況時間復(fù)雜度
平均時間復(fù)雜度的全稱應(yīng)該叫做加權(quán)平均時間復(fù)雜度或者期望時間復(fù)雜度闸餐；
均攤時間復(fù)雜度以及它對應(yīng)的分析方法，攤還分析（或者叫平攤分析）
對于一個數(shù)據(jù)結(jié)構(gòu)進(jìn)行一組連續(xù)操作中矾芙，大部分情況下時間復(fù)雜度都很低舍沙，只有個別情況下時間復(fù)雜度比較高，而且這些操作之間存在前后連貫的時序關(guān)系剔宪，這個時候拂铡，我們就可以將這一組操作放在一塊分析，看是否能將較高時間復(fù)雜度那次操作的耗時葱绒，平攤到其他那些時間復(fù)雜度比較低的操作上感帅。而且，再能夠應(yīng)用均攤時間復(fù)雜度分析的場合地淀，一般均攤時間復(fù)雜度就等于最好情況時間復(fù)雜度失球；均攤時間復(fù)雜度是一種特殊的平均時間復(fù)雜度；
