算法设计基础

算法研究的重要问题类型

1. 查找问题
2. 排序问题
3. 图问题
4. 组合问题
   最优化问题：寻找一个组合对象，能够满足特定的约束条件并使某个函数取得极值
5. 数学问题
6. 几何问题

代码优化技巧

1. 常量计算
   对于在计算中不变的数值和表达式，尽量在说明语句中赋值：
   节省目标代码的执行时间。
2. 算术计算
   1. 尽量使用乘除代替加减
   2. 高次整幂采取降阶操作

      \(P=a*x^4+b*x^3+c*x^2+d*x+e\) 可以修改为\(P+(((a*x+b)*x)+c)*x+d)*x+e\)

   3. 位计算代替除法和取余

      判断奇数x%2!=0可以修改为(x&1)==1

   4. 避免重复计算
      程序中相同的计算结果保留下来
   5. 有利于编译的优化
      尽可能重复的利用存储单元：

      x=a-b;
      y=b-a;
      //x、y的绝对值相等，但编译器无法识别，会使用两个存储单元，应改为
      x=a-b;
      y=-x;
      

   6. 优化逻辑运算
      利用计算逻辑表达式的短路功能，减少逻辑运算
   7. 合理安排条件表达式顺序
      嵌套分支中，执行概率较大的条件表达式放在前面
   8. 改善循环结构
      1. 不滥用循环
         循环次数较少时，尽量不使用循环

         for(int i=0;i<3;i++)
             sum+=a[i];
         //改写为
         sum+=a[0]+a[1]+a[2];
         

      2. 合理安排嵌套
         循环次数较多的，作为内循环
      3. 合并循环
      4. 循环不变式外提
         相同的循环条件下，一次循环完成多种功能
      5. 循环无开关
         循环中出现与循环变量无关的判断，可以在循环外进行判断

             for(int i=0;i<100;i++)
                 if(x>5)
                     c[i]=a[i]+b[i];
                 else
                     c[i]=a[i]-b[i];
             //改写后减少99次判断
             if(x>5)
                 for(int i=0;i<100;i++)
                     c[i]=a[i]+b[i];
             else
                 for(int i=0;i<100;i++)
                     c[i]=a[i]-b[i];