經(jīng)驗總結(jié)

時間復雜度：

同一問題可用不同算法解決，而一個算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進算法。

O(n)也是差不多的意思，也就是說n很大的時候復雜度約等于Cn，C是某個常數(shù)。

O(1)就是說n很大的時候，復雜度基本就不增長了，基本就是個常量C。

代碼實例：去除給定列表中的重復元素

MyList = [1, 2, 4, 7, 2, 7, 4, 8, 3, 9, 1]

ResultList = list()

for item in MyList:

? ? if item not in ResultList:

? ? ? ? ResultList.append(item)

以上代碼可以得到預期的結(jié)果，但是算法存在問題。

如果給定的列表很龐大，會存在以下問題：

1、在if做not in成員判斷的時候，時間復雜度是O(1)；

2、列表的一次性讀取，會很消耗內(nèi)存。

針對問題1，改寫如下：

MyList = [1, 2, 4, 7, 2, 7, 4, 8, 3, 9, 1]

ResultList = list()

ResultSet = set()

for item in MyList:

? ? if item not in ResultSet:

? ? ? ? ResultList.append(item)

? ? ? ? ResultSet.add(item)

set在做成員判斷的時候，時間復雜度是O(1)的，比list要快，規(guī)模越大，效果越明顯。

針對問題2，可以使用布隆過濾器，以后再研究

。。。待續(xù) 。。。

。。。待續(xù)。。。