请选择 进入手机版 | 继续访问电脑版
爱气象,爱气象家园! 

气象家园

 找回密码
 立即注册

QQ登录

只需一步,快速开始

新浪微博登陆

只需一步, 快速开始

搜索
查看: 2332|回复: 0

[混合编程] 插入排序算法的运行时间推导

[复制链接]

新浪微博达人勋

发表于 2017-4-23 16:39:18 | 显示全部楼层 |阅读模式

登录后查看更多精彩内容~

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

x
基本前提:
插入排序算法的运行时间主要取决于:
1,“输入规模”,就是需要排序的向量大小,排序100个数和排序100万个数的时间是不一样的;一般,运行时间与输入规模正相关,所以习惯上把运行时间定义为输入规模的函数,T(n)。“输入规模”如何描述也依赖于具体的问题:
QQ截图20170423160251.png
2,“已排序程度”,排序一个基本排好的向量和排序一个混乱向量的时间是不一样的;规定:执行每行伪代码需要常量的时间,即,第i行每次执行需要时间Ci;
T(n)的化简:
QQ截图20170423161235.png
总时间是每条语句的时间cost和执行次数乘积之和:
QQ截图20170423161751.png
当向量已经排好序,则“最佳情况”的运行时间是:
QQ截图20170423162819.png
运行时间可以表示为an+b,a和b依赖于时间代价(cost),最佳情况是n的线性函数。
当向量反向排序,则“最坏情况”的运行时间是:
QQ截图20170423163228.png
最坏情况的运行时间表示为an^2+bn+c,是n二次函数。
通常,采用最坏情况的运行时间。
最坏情况运行时间Θ:
通常,n的高次项最重要,当输入较大时,低次项和最高次项的系数相对不重要,记最坏情况运行时间为Θ(n2)。次数越高视为运行越慢。
密码修改失败请联系微信:mofangbao
您需要登录后才可以回帖 登录 | 立即注册 新浪微博登陆

本版积分规则

Copyright ©2011-2014 bbs.06climate.com All Rights Reserved.  Powered by Discuz! (京ICP-10201084)

本站信息均由会员发表,不代表气象家园立场,禁止在本站发表与国家法律相抵触言论

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