算法考试复习.docVIP

Algorithm:An algorithm is a finite sequence of instructions, an explicit, step-by-step procedure for solving a problem. ((g(n)):渐进下界 For a given function g(n), we define ((g(n)) by ((g(n)) = { f (n): (( c 0, n 0 ∈ N, s.t. 0 ≤ c g(n) ≤ f (n), for all n ≥ n 0 } Θ(g(n)):渐进紧界 For a given function g(n), we define Θ(g(n)) by Θ(g(n)) = { f (n): (( c1, c2 0, n 0 ∈ N, s.t. 0 ≤ c1 g(n) ≤ f (n) ≤ c2 g(n), for all n ≥ n 0 } O(g(n))：渐进上界 For a given function g(n), we define O(g(n)) by O(g(n)) = { f (n): (( c 0, n 0 ∈ N, s.t. 0 ≤ f (n) ≤ c g(n), for all n ≥ n 0 } Principle of Optimality： An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision. （作为整个过程的最优策略, 无任过去的状态和决策如何, 对当前的决策形成状态而言, 余下的诸决策必须构成最优策略.） Greedy Algorithm： A greedy algorithm makes a locally optimal choice step by step in the hope that this choice will lead to a globally optimal solution. 一个贪婪的算法能够使本地一步一步的最佳选择,希望这个选择将导致一个全局最优解。 NP问题是所有可用多项式时间算法验证其猜测准确性的问题的集合。 Recursion： N!: if(n==0){return1;}else{return(n*Factorial(n-1)); 斐列: if (n=1) return n;else{return(Fib(n-1)+Fib(n-2));} Max：if (i == n)return n; int j = Max(A, n, i+1); if (A[i] = A[j]) return i; return j; 摩根排序： 快速排序： 插入排序： HUFFMAN： N—queen： DFS： M着色： 背包问题： BFS：