1.基础概念
1）算法复杂度
一个算法的时间复杂度，指算法运行的时间。
渐进表达式
转至 https://blog.csdn.net/corivsky/article/details/2772004
一。大O记号
假设f(n)和g(n)的定义域是非负整数，存在两个正整数c和n0，使得n>n0的时候，f(n)≤c*g(n),则f(n)=O(g(n))。可见O(g(n))可以表示算法运行时间的上界。O(g(n))表示的函数集合的函数是阶数不超过g(n)的函数。
例如：f(n)=2*n+2=O(n)
证明：当n>3的时候，2*n +2<3n，所以可选n0=3,c=3，则n>n0的时候，f(n)
现在再证明f(n)=2*n+2=O(n^2)
证明：当n>2的时候，2*n+2<2*n^2，所以可选n0=2,c=2,则n>n0的时候，f(n)
同理可证f(n)=O(n^a)，a>1
二。Ω记号
Ω记号与大O记号相反，他可以表示算法运行时间的下界。Ω（g（n））表示的函数集合的函数是所有阶数超过g(n)的函数。
例如：f(n)=2*n^2+3*n+2=Ω(n^2)
证明：当n>4的时候，2*n^2+3*n+2>n^2，所以可选n0=4,c=1,则n>n0的时候，f(n)>c*(n^2)，所以f(n)=Ω(n^2)。
同理可证f(n)=Ω(n),f(n)=Ω(1)
三。Θ记号
Θ记号介于大O记号和Ω记号之间。他表示，存在正常数c1,c2,n0，当n>n0的时候，c1*g(n)≤f(n)≤c2*g(n)，则f(n)=Θ(g(n))。他表示所有阶数与g(n)相同的函数集合。
四。小o记号
f(n)=o(g(n))当且仅当f(n)=O(g(n))且f(n)≠Ω(g(n))。也就是说小o记号可以表示时间复杂度的上界，但是一定不等于下界。
2）重要的复杂度
O(1)表示常数运行时间
O(logn)表示对数运行时间
O(n)表示线性运行时间
O(nlogn)表示对数线性运行时间
O(n**k)表示多项式运行时间，注意k是常数
O(c**n)表示指数运行时间，这时常数C为底数，复杂度为c的n次方
3）排序算法
排序算法大体可分为两种：一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。
下面是一个总的表格，大致总结了我们常见的所有的排序算法的特点。
更多见：http://blog.csdn.net/u012796139/article/details/43889449
4散列表
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。（来源于百度百科）
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
2.错题收集：
网友评论