经验总结

时间复杂度：

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

O(n)也是差不多的意思，也就是说n很大的时候复杂度约等于Cn，C是某个常数。

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)

以上代码可以得到预期的结果，但是算法存在问题。

如果给定的列表很庞大，会存在以下问题：

1、在if做not in成员判断的时候，时间复杂度是O(1)；

2、列表的一次性读取，会很消耗内存。

针对问题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要快，规模越大，效果越明显。

针对问题2，可以使用布隆过滤器，以后再研究

。。。待续 。。。

。。。待续。。。