中国仿真技术论坛,CAE/CAD/FEM,有限元分析论坛,ANSYS论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 130|回复: 0

算法效率分析

[复制链接]

该用户从未签到

45

主题

46

帖子

38

积分

技术员

Rank: 1

积分
38
发表于 2019-3-14 15:31:45 | 显示全部楼层 |阅读模式

算法是一系列解决问题的明确指令,对于一定符合规范的输入,能够在有限时间内获得要求的输出。从实际问题的提出到设计合适的算法再到正确性的分析以及算法效率的分析,最后为算法编写代码,一步步得到问题的解决方案。


图1.算法的概念

图2.算法设计分析过程

对算法效率的分析,需要指出有两种算法效率:时间效率和空间效率,分指算法运行速度和需要的额外空间。由于技术革新,对于大多数问题,速度上效率的提高远大于空间上的提高。在研究算法效率上提出一般性框架。
定义1:如果存在正常数c和使得当,则记为
定义2:如果存在正常数c和使得当,则记为
定义3当且仅当
定义4:如果,则
定义的目的实在函数之间建立相对的级别。可直观的理解为增长率小于等于增长率大于等于增长率等于增长率小于

法则1:如果,那么
(a)
(b)
法则2:如果是k次多项式,则
法则3:对任意常数k,
下面以最大子序列和问题的四种解决方法来分析算法的效率问题。

最大子序列和:给定整数(可能含负数),求最大值(若所有整数为负,则最大子序列和为0)


算法
1
2
3
4
时间
输入大小/m
N=10
0.00103
0.00045
0.00066
0.00034
N=100
0.47015
0.01112
0.00486
0.00063
N=1000
448.77
1.1233
0.05843
0.00333
N=10000
NA
111.13
0.68631
0.03042
N=100000
NA
NA
8.0113
0.29832



回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

无觅相关文章插件

QQ|申请友链|Archiver|手机版|小黑屋|广告服务|中国仿真技术论坛 ( 苏ICP备16004717号

GMT+8, 2019-5-20 02:28 , Processed in 0.111386 second(s), 34 queries .

Powered by Discuz! X3.2 Licensed

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表