目录

1.代码优化

for循环

位运算

输入输出

打表法（骗分而已）

数组合并

 减少函数参数

递归（搜索）剪枝

 数组按行访问

分块

字符串

2.常出的错误

判断相等

拼写错误

---

 

1.代码优化

• for循环

     未优化代码：

for(i=0;i<sqrt(n);i++)

      for（单次表达式;条件表达式;末尾循环体），结束条件写在中间，结束一轮循环就会进行比较判断，如果循环量比较大，sqrt函数就会运行多次。

     优化方式：

       用变量保存，不在for循环里面有函数。while循环等类似。

     优化代码：

int bound = sqrt(n);
for(int i=0;i<bound;i++)

 或者（如果倒序对函数体内没影响的话）

for(int i=sqrt(n)-1;i>-1;i--)

• 位运算

     位运算在判断整型变量奇偶、取余、交换变量等方面都能加速。单独写了一篇文章，欢迎分享更多位运算的妙用。  

     c语言位运算的妙用-程序优化

• 输入输出

     c语言的输入、输出scanf与printf是比c++的cin和cout快的，所以，有大量输入输出时，选择c语言的。

     c/c++输入输出总结

• 打表法（骗分而已）

        打表法就是将题目中需要的答案提前算出来，存到数组里。这种方法只需要将程序挂着，然后去做别的题。算出结果后，复制到数组里面。最终取答案程序时间复杂度为O(1)，空间复杂度为O(n)；
                                                                                                                                                                             ——沃兹·基梭德

• 数组合并

    将相关数据放在一起，尽管放在不同数组时，不会进行排序等操作造成下标的不对应，但是在Cache中两个数组的数据不一定放在一起。可以用结构体，例如，学生。

修改前：

int id[maxn];
string name[maxn];

修改后：

typedef struct student
{
   int id;
   string name;
}student;

student S[maxn];

•  减少函数参数

         在使用递归写法时，可以将数组等设置为全局变量，减少函数的参数，能减少一定的时间。

• 递归（搜索）剪枝

       减少不必要的搜索，递归调用时会有函数栈，浪费时间。

      递归-简单背包问题（修剪递归树，含全部代码）

•  数组按行访问

        学过计算机系统结构的同学应该知道，对于二维数组，按行访问能降低Cache不命中率，能够进行部分优化。一般老师教的都是按行访问优先。

• 分块

       在矩阵运算时，先对子块进行运算。博主目前对矩阵运算涉及很少，遇到时再更。

• 字符串

       使用empty()函数判断字符串为空，比使用size()==0判断，效率更高。

2.常出的错误

• 判断相等

       我们做数学时，总是用“=”表示相等，而在c/c++中是赋值，相等是“==”。常出错误是在条件判断时，把相等错写成赋值。

    错误代码：

if(i=1)cout<<“只有1个”<<endl;
else cout<<“没有了”<<endl;

     防止方式：

      在想判断相等时，将数值写在左侧。例如,1==i，这样是没有任何问题的，但是，假如你不小心写错了，写成了1=i，编译器会报错，因为你把变量赋给了数值。

     纠正代码：

if(1==i)cout<<“只有1个”<<endl;
else cout<<“没有了”<<endl;

• 拼写错误

有时出错，检查代码，可能是因为 int mian 或者 flase等拼写错误造成的，感觉很可笑，又浪费了时间。

        防止方式：

        利用宏定义，#define 错误的 正确的， 例如 #define flase false。

未完，待续...

更多数据结构与算法实现：数据结构（严蔚敏版）与算法的实现（含全部代码）

有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。