算法导论
• A technique to prove that an algorithm is correct. Identify a loop-invariant .
• O(g(n)) = {f(n): There exist positive constants c and n0 suchthat 0≤f(n) ≤cg(n) for all n≥n0 }
--O(.) is used to asymptotically upper bound a function. 用于渐近地定义函数的上界
--O(.) is used to bound worst-case running time. 用于限制最坏情况下的运行时间
• Ω(g(n)) = {f(n): There exist positive constants c and n0 suchthat 0 ≤ cg(n) ≤f(n) for all n≥n0 }
--We use Ω-notation to give a lower bound on a function. 我们使用Ω-符号来给函数下限
• Θ(g(n)) = {f(n): There exist positive constants c1, c2 and n0 such that 0 ≤ c1g(n) ≤f(n) ≤c2g(n) for all n≥n0 } 相当于 "扔掉低阶项并忽略最高阶项前的系数"
--We use Θ-notation to give a tight bound on a function. 紧致界
-- f(n) =Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n))
基于比较的排序算法 这类排序包括插入，归并，堆，快速的等排序，共同点是都需要对数据进行比较，因此，时间复杂度不能突破 O(NlogN)
快排有最坏情况；插排、冒泡有最好情况；堆排、归并时间复杂度各情况一致
稳定性：插排、冒泡、归并、桶排、计排、基数 不稳定：快排、选排、堆排、希排
非基于比较的排序 对输入数据有额外限制之后，可以使用一些时间复杂度更小的算法，如计数排序，桶排序，基数排序。
计数排序的理解与实现
桶排序
基数排序
