[C语言] 数据结构-算法效率的度量方法-事前分析估算方法
2023-02-18 15:47:02 时间
事前分析估算方法:在计算机程序编制前,依据统计方法对算法进行估算,抛开与计算机硬件软件有关的因素,一个程序的运行时间,依赖于算法的,好坏和问题的输入规模,所谓问题输入规模是指输入量的多少
推导过程,比如计算1+2+3+...100:
int i,sum=0,n=100 //执行1次
for(i=1;i<=n;i++) //执行n+1次
{
sum=sum+i; //执行n次
}
去掉头尾循环判断,执行了n次
第二种算法:
int sum=0,n=100 //执行1次
sum=(1+n)*n/2; //执行1次
去掉头尾循环判断,执行了1次
延伸一下:
int i,x,j,sum=0,n=100 //执行1次
for(i=1;i<=n;i++) //执行n+1次
{
for(j=1;i<=n;j++){
x++;
sum=sum+x; //执行n*n次
}
}
循环部分的代码整体需要执行n^2次
因此当问题输入规模是n时,f(n)作为一个函数操作数量分别为
f(n)=n
f(n)=1
f(n)=n^2
由于函数的渐进增长,n的值越大,差异也就越大,因此我们在判断一个算法时
一般都忽略掉常数项,忽略掉次要项,只关注最高次项,关注最高阶项的阶数
相关文章
- [PHP] 重要操作手机短信验证逻辑梳理
- [css] position:fixed居中问题
- [PHP] xml转对象函数simplexml_load_string
- [MySQL] 理解MySQL索引合并index_merge
- [MySQL] 理解mysql间隙锁
- MagicAjax 使用介绍(翻译)
- 第三产业的企业的信息化系统的价格机制
- MagicAjax 简单使用介绍(翻译)
- (转帖)asp.net调试错误解决方法收集(1)
- MagicAjax Features (MagicAjax特点 0.30版) (翻译)
- 疑是Microsoft Enterprise Library June 2005的一个小bug (续)
- 疑是Microsoft Enterprise Library June 2005的一个小bug
- MagicAjax 0.30版的更新(翻译)
- 【愚公系列】2022年12月 .NET CORE 即时通讯-使用SignalR进行井字游戏
- Winform自动更新之AutoUpdater.NET
- [MySQL] 理解InnoDB并发高的原因
- 自己动手基于 Redis 实现一个 .NET 的分布式锁类库
- [MySQL] in 子查询出现DEPENDENT SUBQUERY问题
- [MySQL] group by 聚合函数的原理和聚合限制原因SELECT list is not in GROUP BY clause and contains nonaggregated column
- [MySQL]mysql的ANY_VALUE()函数 解决 ONLY_FULL_GROUP_BY 模式