|
全文內(nèi)容主要源于極客大學(xué)的算法課，僅作為筆記使用。
1、數(shù)組數(shù)組：在內(nèi)存中，占用連續(xù)內(nèi)存空間的，有序的元素序列。
數(shù)組元素的類型沒(méi)有要求，即為泛型。 底層原理當(dāng)申請(qǐng)數(shù)組時(shí)，內(nèi)存管理器分配一個(gè)連續(xù)的內(nèi)存地址。每一個(gè)地址可以直接通過(guò)內(nèi)存管理器進(jìn)行訪問(wèn)。
如下圖所示，即為數(shù)組相應(yīng)的內(nèi)存地址：
直接訪問(wèn)的話，訪問(wèn)第一個(gè)元素和訪問(wèn)任意一個(gè)元素，時(shí)間復(fù)雜度都是一樣的，為 O(1)。 數(shù)組特性訪問(wèn)速度快訪問(wèn)數(shù)組時(shí)，其實(shí)是利用指針，即內(nèi)存地址，直接訪問(wèn)對(duì)應(yīng)內(nèi)存地址中的數(shù)值，所以訪問(wèn)速度非?？臁?br>訪問(wèn)數(shù)組的時(shí)間復(fù)雜度：常數(shù)復(fù)雜度 O(1) 刪除和插入: O(n)如下圖所示：
當(dāng)向數(shù)組中插入元素 D 時(shí)，首先要將 E、F、G 都向下挪動(dòng)一個(gè)位置，然后將 index=3 的地址值賦值為 D。
同理： Array 各操作時(shí)間復(fù)雜度prepend: O(n)，正常情況下是 O(n)，但是可以進(jìn)行特殊優(yōu)化到 O(1)。初始化時(shí)申請(qǐng)稍大一些的內(nèi)存空間，然后在數(shù)組最開(kāi)始預(yù)留一部分空間，然后 prepend 操作只需要把頭下標(biāo)千一一個(gè)位置即可。
append: O(1)
lookup: O(1)
insert: O(n)
delete: O(n) 2、鏈表（LinkedList）概念鏈表：元素由 Value 和 next 組成，next 指向下一個(gè)元素，在內(nèi)存中是非連續(xù)空間。鏈表元素一般由 class 定義。
單向鏈表：如果只有一個(gè) next 指針，是單向鏈表。
雙向鏈表：如果由兩個(gè)指針，next 指向下一個(gè)元素，先前指針 prev 或 previous 指向上一個(gè)元素。一般頭叫做 Head，尾叫做 Tail。
循環(huán)鏈表：如果 next 指向 Head，叫做循環(huán)鏈表。 LinkedList 定義最簡(jiǎn)單的鏈表定義： class LinkedList {
Node head; // head of list
/* Linked List Node */
class Node {
int data;
Node next;
Node(int d) { data = d; }
}
} 插入和刪除增加節(jié)點(diǎn)
節(jié)點(diǎn)增加步驟：刪除節(jié)點(diǎn)刪除節(jié)點(diǎn)為增加節(jié)點(diǎn)的逆操作。 刪除節(jié)點(diǎn)步驟： 由此可見(jiàn)，鏈表的增加和刪除，沒(méi)有引起整個(gè)鏈表的群移操作，也不需要復(fù)制元素。所以移動(dòng)或修改鏈表的效率非常高，時(shí)間復(fù)雜度為 O(1)。
但是，正因?yàn)殒湵淼倪@種特性，當(dāng)訪問(wèn)中間節(jié)點(diǎn)時(shí)，必須從 Head Node 一步一步往后找，時(shí)間復(fù)雜度為 O(n) 鏈表各操作時(shí)間復(fù)雜度3、跳表 Skiped List科學(xué)家在數(shù)組和鏈表基礎(chǔ)上，優(yōu)化了新的數(shù)據(jù)結(jié)構(gòu)，即 跳表。
主要關(guān)注：升維思想 + 空間換時(shí)間 跳表的特點(diǎn)注意：只能用于元素有序的情況。
所以，跳表對(duì)標(biāo)的是平衡樹(shù)（VAL Tree）和二分查找，是一種插入/刪除/查找 都是 O(log n) 的數(shù)據(jù)結(jié)構(gòu)。
它最大的優(yōu)勢(shì)是原理簡(jiǎn)單、容易實(shí)現(xiàn)、方便擴(kuò)展、效率更高。因此在一些熱門的項(xiàng)目里用于替代平衡樹(shù)，如 Redis、LevelDB 等。 如何給有序的鏈表加速有序一維數(shù)據(jù)結(jié)構(gòu)加速理念：經(jīng)常采用的方式就是升維，也就是說(shuō)變成二維。
（1）加一級(jí)索引
第一級(jí)索引指向的是 next.next
（2）加二級(jí)索引
二級(jí)索引 next 指向的是一級(jí)索引鏈表的 next.next
（3）多級(jí)索引
以此類推，加多級(jí)索引如下圖所示：
跳表查詢的時(shí)間復(fù)雜度n/2、n/4、n/8，第 k 級(jí)索引節(jié)點(diǎn)的個(gè)數(shù)就是 n/(2k)
假設(shè)索引有 h 級(jí)，最高級(jí)的索引有 2 個(gè)結(jié)點(diǎn)。n / (2h) = 2，從而求得 h = log2(n) - 1 假設(shè)原始鏈表要查詢 1024 次的話，那么跳表的時(shí)間復(fù)雜度是 log2(n)，即 10 次就可以找到元素。 現(xiàn)實(shí)中的跳表如下圖所示，現(xiàn)實(shí)中的跳表，由于多次的增加和刪除，導(dǎo)致有些索引并不是完全工整的，最后經(jīng)過(guò)多次改動(dòng)后，有些地方的索引會(huì)多跨幾步，有些地方會(huì)少跨或只跨兩步。
維護(hù)成本相對(duì)較高，比如增加或刪除一個(gè)元素的話，索引要更新一遍，此時(shí)時(shí)間復(fù)雜度就變?yōu)?Logn 了。
空間復(fù)雜度跳表的空間復(fù)雜度為 O(n)，但是比原始鏈表要多很多。
|
