一. 简答题的基本内容(30分) 1. 记号O、W、[if !vml] [endif] 的意义; O:存在n0>0、c>0, 使得n>=n0有f(n) <=c*g(n) Ω:存在n0>0、c>0, 使得n>=n0有f(n) >=c*g(n) Θ:如果T(n)是Θ(g(n)), T(n)是O(g(n)), Ω(g(n)) 2. 分治法的基本步骤; 1.分解:将原问题划分成为若干个规模较小并且相互独立,与原问题形式相同的子问题。 2.解决: 若子问题规模较小而容易被解决就直接解,否则递归地解决各个子问题。 3.合并: 将各个子问题的解合并...