算法分析与计算复杂性.pptx

7.6 算法分析与计算复杂性;算法是正确的吗？;算法获得的解是最优的吗？;算法的复杂性分析;示例;分析： 1.语句int num1, num2;的频度为1； 语句i=0;的频度为1； 语句in; i++; num1+=1; j=1; 的频度为n； 语句j=n; j*=2; num2+=num1;的频度为n*log2n； T(n) = 2 + 4n + 3n*log2n 2. 忽略掉T(n)中的常量、低次幂和最高次幂的系数 f(n) = n*log2n 3. lim(T(n)/f(n)) = (2+4n+3n*log2n) / (n*log2n) = 2*(1/n)*(1/log2n) + 4*(1/log2n) + 3 当n趋向于无穷大，1/n趋向于0，1/log2n趋向于0 所以极限等于3。 T(n) = O(n*log2n);1) 加法规则 T(n,m) = T1(n) + T2(n) = O (max ( f(n), g(m) ) 2) 乘法规则 T(n,m) = T1(n) * T2(m) = O (f(n) * g(m)) 3) 一个特例（问题规模为常量的时间复杂度） 在大O表示法里面有一个特例，如果T1(n) ＝ O(c)， c是一个与n无关的任意常数，T2(n) = O ( f(n) ) 则有 T(n) = T1(n) * T2(n) = O ( c*f(n) ) = O( f(n) ) 也就是说，在大O表示???中，任何非0正常数都属于同一数量级，记为O(1)。 ;贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。;;Thank you~