数据结构----效率问题
数据结构----效率问题
一.衡量效率
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.一般会选择递归、分治、动态规划等方法提升时间效率（空间换时间）
