算法导论需要具备哪些基础知识
算法导论需要具备的基础知识有：
1、计算机算法：是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述。
2、概率分析：又称风险分析，是通过研究各种不确定性因素发生不同变动幅度的概率分布及其对项目经济效益指标的影响，对项目可行性和风险性以及方案优劣作出判断的一种不确定性分析法。概率分析常用于对大中型重要若干项目的评估和决策之中。
3、随即算法：是一个概念图灵机，也就是在算法中引入随机因素，即通过随机
算法导论
• 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) 快排有最坏情况；插排、冒泡有最好情况；堆排、归并时间复杂度各情况一致 稳定性：插排、冒泡、归并、桶排、计排、基数 不稳定：快排、选排、堆排、希排 非基于比较的排序 对输入数据有额外限制之后，可以使用一些时间复杂度更小的算法，如计数排序，桶排序，基数排序。 计数排序的理解与实现 桶排序 基数排序
