0
算法学习(第一部分)-性能分析
source link: https://silasmichealson.github.io/2022/03/12/%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0-%E7%AC%AC%E4%B8%80%E9%83%A8%E5%88%86-%E6%80%A7%E8%83%BD%E5%88%86%E6%9E%90/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
算法学习 (第一部分)
第一部分 性能分析
1.时间复杂度
问题计算所需时间同问题规模n的关系,采用大O表示法.
常数阶O(1)-> 对数阶O(log2n)-> 线性阶O(n) ->线性对数阶O(nlog2n)->平方阶O(n2)->立方阶O(n3),…，-> k次方阶O(nk)->指数阶O(2n)。
随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
(1).举个例子
求:x的n次方
int function1(int x,int n){
int result = 1;
for(int i = 0 ;i <ｎ；ｉ＋＋）
｛
result *= x;
}
return result;
}
int function2(int x,int n){
if(n == 0) return 1;
return function2(x,n-1);
}
int function3(int x,int n){
if(n == 0) return 1;
if(n%2 == 1) return function3(x,n/2)*function3(x,n/2)*x;
return function3(x,n/2)*function3(x,n/2);
}
int function4(int x,int n){
if(n == 0) return 1;
int t = function4(x,n/2)
if(n%2==1) return t*t*x;
return t*t;
}
可以看到不同的方法可以使软件的时间空间复杂度截然不同
2.c++的内存管理
(1)理解c++的内存管理
(2)理解为何需要内存对齐?
- 不是所有的硬件平台都允许访问任意内存地址的数据,某些平台只能在一些地址获取特定类型的数据,否则抛出硬件异常,为了同一程序在不同平台运行,需要内存对齐
- 对齐内存后虽然会损失一部分空间,可是能极大提升cpu访问内存的速率(具体原因理解cpu是按块读取内存的,对齐使访问更直接)
3.空间复杂度
同理 所需空间同问题规模的关系也可以使用大o表示法,注意空间复杂度为O(1)也成为就地执行.一般的我们使用空间来换取时间.
(1) 举个例子
int feibo1(int n)
{
//完全的递归
if(n<=0) return 0;
if(n==1||n==2) return 1;
if(n==3) return 2;
else return feibo1(n-1)+feibo1(n-2);
}
int feibo2(int first,int second,int n)
{
//精简解法 应当理解
if(n<=0) return 0;
if(n<3) return 1;
if(n ==3) return first+second;
else return feibo2(second,first+second,n-1);
}
int feibo3(int n)
{
//使用数组存储
if(n<=0) return 0;
if(n==1||n==2) return 1;
vector<int> num{1,1};
num.reserve(n+2);
vector<int>::iterator it;
for(int i = 0; i < n-2 ;i++)
{
num.push_back(num.at(i)+num.at(i+1));
}
return num.back();
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK