時(shí)間復(fù)雜度
1.一個(gè)算法是由控制結(jié)構(gòu)（順序糊昙、分支荆永、循環(huán)3種）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的鹤盒，則算法時(shí)間取決于兩者的綜合效果。為了便于比較同一問(wèn)題的不同算法褐隆，通常的做法是污它，從算法中選取一種對(duì)于所研究的問(wèn)題（或算法類型）來(lái)說(shuō)是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量庶弃。
一般情況下算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f(n),算法的時(shí)間度量記作 T(n) = O(f(n)),它表示隨著問(wèn)題規(guī)模n的增大衫贬，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作算法的漸近時(shí)間復(fù)雜度歇攻，簡(jiǎn)稱時(shí)間復(fù)雜度固惯。
例如 for(i=1;i < n; I++),該算法的時(shí)間復(fù)雜度是 O(n).
線性表
簡(jiǎn)單的說(shuō)一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列。
稍微復(fù)雜的線性表中缴守，一個(gè)數(shù)據(jù)元素可以有若干個(gè)數(shù)據(jù)項(xiàng)組成葬毫，在這種情況下，常把數(shù)據(jù)元素成為記錄屡穗，含有大量記錄的線性表又稱為文件贴捡。注意:線性表中的數(shù)據(jù)元素可以是各種各樣的，但是同一線性表中元素必定具有相同特性村砂。
線性表的特點(diǎn)：
在數(shù)據(jù)元素的非空有限集中烂斋，（1）存在唯一的一個(gè)被稱為‘第一個(gè)’的數(shù)據(jù)元素；（2）存在唯一的一個(gè)被稱為‘最后一個(gè)’的數(shù)據(jù)元素；（3）除了第一個(gè)以外汛骂，集合中的每個(gè)元素都只有一個(gè)前驅(qū)罕模；（4）除了最后一個(gè)數(shù)據(jù)元素以外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼香缺。
線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)
1.線性表的順序表示指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素手销。換句話說(shuō)，以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來(lái)表示線性表內(nèi)元素之間的邏輯關(guān)系图张。
LOC(ai) = LOC(a1) + (n - 1)*l;
由此锋拖，只要確定了存儲(chǔ)線性表的起始位置，線性表中任一數(shù)據(jù)元素都可以隨機(jī)存取祸轮，所以線性表的順序存儲(chǔ)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)兽埃。
插入和刪除元素是有大量的數(shù)據(jù)元素移動(dòng)，時(shí)間復(fù)雜度為O(n)
鏈?zhǔn)酱鎯?chǔ)
結(jié)點(diǎn)：包含指針域和數(shù)據(jù)域
鏈表的存取必須從頭指針開始進(jìn)行适袜，頭指針指示鏈表中第一結(jié)點(diǎn)的存儲(chǔ)位置柄错。同時(shí)，由于最后一個(gè)數(shù)據(jù)元素沒(méi)有直接后繼苦酱，則線性鏈表中最后一個(gè)結(jié)點(diǎn)的指針為空（NULL）
有時(shí)售貌，我們?cè)趩捂湵淼牡谝粋€(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)疫萤。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息颂跨，也可以存儲(chǔ)線性表的長(zhǎng)度類的附加信息，頭結(jié)點(diǎn)的指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針扯饶，若線性表為空表恒削，則頭結(jié)點(diǎn)的指針域?yàn)榭铡?br>
單鏈表的數(shù)據(jù)查找必須從頭指針出發(fā)尋找，因此尾序，單鏈表是非順序存取的存儲(chǔ)結(jié)構(gòu)钓丰。
鏈表的插入和刪除時(shí)，時(shí)間復(fù)雜度也是O(n),因?yàn)樾枰獜念^結(jié)點(diǎn)開始遍歷找到需要?jiǎng)h除或者插入的位置.但是由于鏈表在空間的合理利用上和插入每币、刪除時(shí)不需要移動(dòng)等優(yōu)點(diǎn)携丁，因此在很多場(chǎng)合下，它是線性表的首選存儲(chǔ)結(jié)構(gòu)兰怠。然而梦鉴，它也存在著實(shí)現(xiàn)某些基本操作，如求線性表的長(zhǎng)度時(shí)不如順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)痕慢。
