排序算法(2)-算法的复杂度

技术分享  / 只看大图  / 倒序浏览   ©

#楼主# 2020-2-11

跳转到指定楼层

马上注册,分享更多源码,享用更多功能,让你轻松玩转云大陆。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
1. 算法的时间复杂度

1.1 度量一个程序(算法)执行时间的两种方法

1) 事后统计的方法
这种方法可行, 但是有两个问题:

  • 一是要想对设计的算法的运行性能进行评测,需要实际运行该程序;
  • 二是所得时间的统计量依赖于计算机的硬件、软件等情况因素, 这种方式,要在同一台计算机的相同状态下运行,才气比较那个算法速度更快。
2) 事前估算的方法
通过分析某个算法的时间复杂度来判断哪个算法更优
1.2 时间频度

1.基本先容

时间频度:
一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。[举例说明]
2.举例说明-基本案例

比如计算 1-100 所有数字之和, 我们设计两种算法:
092502ufmf400jh3d44dcf.png
3.举例说明-忽略常数项

092503yv2jj0el0tk0ln7t.png
结论:

  • 2n+20 和 2n 随着 n 变大,执行曲线无限接近, 20 可以忽略
  • 3n+10 和 3n 随着 n 变大,执行曲线无限接近, 10 可以忽略
4.举例说明-忽略系数

092504egs7a93y9v6g9kv7.png
结论:
<ol>
随着 n 值变大,5
分享淘帖
回复

使用道具

您的回复是对作者最大的奖励

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

本版积分规则

关于作者

  • 主题

    11

  • 帖子

    11

  • 关注者

    0

Archiver|手机版|小黑屋|云大陆 | 赣ICP备18008958号-4|网站地图
Powered by vrarz.com!  © 2019-2020版权所有云大陆