数据结构----效率问题

数据结构----效率问题

一.衡量效率

1.衡量效率的两个维度

1.时间维度：时间复杂度：Time Complexity

时间复杂度是代码总的运行次数（粗糙）

2.空间维度：空间复杂度：Space Complexity

空间复杂度是额外申请的空间

3.注意：

​ 1.复杂度表示方法为 O()

2. 如果时间和空间不能同时达到一个理想状态，时间优先，用空间换时间 。一些特殊的应用场合会用空间换时间

3. 一般算循环的时间复杂度，看循环体执行几次就可以

   也可以看代码总执行次数是看总共执行了多少条语句

2.复杂度要求

1.多项级的运算结果，只保留最大项（最高次幂）

2.常系数省舍去

3.如果程序在有限棵树的资源消耗内即可完成(与n无关)，那么复杂度为O(1)

3.看下面代码判断时间复杂度

//时间复杂度为 O(n)
for(int i=0;i<n;i++){cout<<i<<endl;
}//时间复杂度为 O(log2的n次方)
for(int i=1;i<=n;i*=2){cout<<i<<endl;
}//时间复杂度为 O(n的平方)
for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cout<<i<<"  "<<j<<endl;}
}//时间复杂度为 O(n的立方)
for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){for(int k=1;k<=j;k++){cout<<i<<"  "<<j<<endl;}}
}

6.关于复杂度计算的一些经验性结论

1.单纯的顺序和选择结构，时间复杂度为O(1)

2.一般的一层循环时间复杂度为O(n)

3.两个并列的循环，时间复杂度max(O(m),O(n))

4.一般的两层循环嵌套，时间复杂度是O(n的平方)

5.一般会选择递归、分治、动态规划等方法提升时间效率（空间换时间）