首先了解什么叫做數(shù)據(jù)結(jié)構(gòu)。
數(shù)據(jù)結(jié)構(gòu)，英文名稱Data Structure，代表存儲(chǔ)數(shù)據(jù)的不同方式。
接下來(lái)，了解一下算法。
算法，英文名稱Algorithm，代表的是同一種問(wèn)題的不同的解決方法。
算法往往針對(duì)的是特定的數(shù)據(jù)結(jié)構(gòu)的：
不同的數(shù)據(jù)結(jié)構(gòu)所使用的算法不同。
每種數(shù)據(jù)結(jié)構(gòu)在特定的時(shí)間問(wèn)題中的算法表現(xiàn)都不相同。
眾所周知，在編程領(lǐng)域有很多的算法，雖然結(jié)果目的都一樣，但是他們解決問(wèn)題的思路卻不盡相同，我們?nèi)绾闻袛嘁粋€(gè)算法的優(yōu)劣呢？
對(duì)于計(jì)算機(jī)來(lái)說(shuō)，常用的測(cè)量標(biāo)準(zhǔn)有兩個(gè)，一個(gè)是時(shí)間測(cè)算，一個(gè)是空間測(cè)算。通常我們使用這兩種測(cè)量標(biāo)準(zhǔn)來(lái)判斷算法的優(yōu)劣。
時(shí)間測(cè)算：時(shí)間越少越好。
空間測(cè)算：空間浪費(fèi)越少越好。
long before = System.currenTimeMillis();//記錄算法的開(kāi)始時(shí)間
long after= System.currenTimeMillis();//記錄算法的結(jié)束時(shí)間
System.out,println(after - before);
我們可以使用上述的代碼來(lái)測(cè)算整個(gè)算法進(jìn)行測(cè)算所耗費(fèi)的時(shí)間，從而在時(shí)間測(cè)算這個(gè)角度判斷一個(gè)算法的好壞。
在進(jìn)行測(cè)算時(shí)，可能因?yàn)橛?jì)算機(jī)的性能比較好而無(wú)法比較直觀的發(fā)現(xiàn)兩個(gè)算法之間細(xì)微的差別。
這個(gè)時(shí)候我們用到了一個(gè)方法，叫做"幅度不夠，循環(huán)來(lái)湊"，沒(méi)辦法直觀的看出算法之間的差別，那我們就將算法進(jìn)行循環(huán)，這樣就能體現(xiàn)出算法之間的區(qū)別了。
Big O標(biāo)記
時(shí)間-問(wèn)題(數(shù)據(jù))規(guī)模
不考慮必須要做的操作
循環(huán)、賦初值、程序初始化…
不考慮常數(shù)項(xiàng)
2n–n
不考慮低次項(xiàng)
n2+n – n2
學(xué)術(shù)上表示一個(gè)算法的優(yōu)劣。先引入兩個(gè)概念
時(shí)間復(fù)雜度：計(jì)算機(jī)解決問(wèn)題的時(shí)間隨著問(wèn)題規(guī)模的擴(kuò)大時(shí)間進(jìn)行變化的規(guī)律。
空間復(fù)雜度：計(jì)算機(jī)解決問(wèn)題時(shí)所占用的空間隨著時(shí)間的擴(kuò)大而進(jìn)行變化的規(guī)律。
下面，根據(jù)例子來(lái)具體的了解時(shí)間復(fù)雜度與空間復(fù)雜度。
1、訪問(wèn)數(shù)組的某個(gè)位置的值
隨著數(shù)組規(guī)模的擴(kuò)大，觀察所花費(fèi)時(shí)間的變化。
訪問(wèn)數(shù)組最后一個(gè)位置的數(shù)，隨著數(shù)組規(guī)模擴(kuò)大，花費(fèi)時(shí)間并不會(huì)發(fā)生改變。
數(shù)組要訪問(wèn)任意位置的值，所需要計(jì)算的是數(shù)組的偏移量，都是計(jì)算偏移量需要花費(fèi)的時(shí)間。這是必須要做的操作。
這時(shí)，我們把這個(gè)算法的時(shí)間復(fù)雜度稱之為O(1)。表示這個(gè)時(shí)間復(fù)雜度是一個(gè)常數(shù)，無(wú)論數(shù)組規(guī)模如何擴(kuò)大，所花費(fèi)的時(shí)間都是一個(gè)常數(shù)。
2、訪問(wèn)鏈表的某個(gè)位置的值
根據(jù)上面的例子，我們不難得出：訪問(wèn)鏈表的第一個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度是O(1)，但是，在測(cè)算時(shí)間復(fù)雜度的時(shí)候，我們所考慮的都是最壞情況下的時(shí)間復(fù)雜度。
所以，我們對(duì)訪問(wèn)鏈表測(cè)算時(shí)間復(fù)雜度的情況是訪問(wèn)鏈表的最后一個(gè)值。
因?yàn)樵阪湵磉M(jìn)行訪問(wèn)時(shí)，我們無(wú)論如何都需要從第一個(gè)數(shù)開(kāi)始進(jìn)行訪問(wèn)，這里我們就可以得出，訪問(wèn)第一個(gè)數(shù)的時(shí)間復(fù)雜度是O(1)，訪問(wèn)第100個(gè)數(shù)的時(shí)間復(fù)雜度是O(100)。由此，可以得出訪問(wèn)鏈表的某個(gè)位置的值的時(shí)間復(fù)雜度是O(n)。
O(n)表示的是：當(dāng)數(shù)據(jù)規(guī)模擴(kuò)大時(shí)，所花費(fèi)的時(shí)間隨著進(jìn)行線性的擴(kuò)大。
每種算法的時(shí)間復(fù)雜度不盡相同，有的是O(n2),有的是O(n3),還有O(log n)等等。
總結(jié)的不是很全面，這里有算法時(shí)間復(fù)雜度和空間復(fù)雜度的詳細(xì)視頻介紹，關(guān)注轉(zhuǎn)發(fā)私信“算法”，即可獲得視頻。
