程序中的时间复杂度是怎么计算的？_百度知道
程序中的时间复杂度是怎么计算的？
答题抽奖
首次认真答题后
即可获得3次抽奖机会，100%中奖。
采纳数：398
获赞数：2735
算法复杂度的介绍，见百科：时间复杂度时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。计算方法1. 一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f（n），因此，算法的时间复杂度记做：T（n）=O（f（n））分析：随着模块n的增大，算法执行的时间的增长率和f（n）的增长率成正比，所以f（n）越小，算法的时间复杂度越低，算法的效率越高。2. 在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数量级（它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n））例：算法：for（i=1;i&=n;++i）{for(j=1;j&=n;++j){c[ i ][ j ]=0; //该步骤属于基本操作 ，执行次数：n的平方 次for(k=1;k&=n;++k)c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 ，执行次数：n的三次方 次}}则有 T（n）= n的平方+n的三次方，根据上面括号里的同数量级，我们可以确定 n的三次方 为T（n）的同数量级则有f（n）= n的三次方，然后根据T（n）/f（n）求极限可得到常数c则该算法的 时间复杂度：T（n）=O（n^3） 注：n^3即是n的3次方。3.在pascal中比较容易理解，容易计算的方法是：看看有几重for循环，只有一重则时间复杂度为O（n）,二重则为O（n^2），依此类推，如果有二分则为O(logn)，二分例如快速幂、二分查找，如果一个for循环套一个二分，那么时间复杂度则为O(nlogn)。分类按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，k次方阶O(n^k), 指数阶O(2^n) 。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。关于对其的理解《数据结构（C语言版）》------严蔚敏 吴伟民编著 第15页有句话&整个算法的执行时间与基本操作重复执行的次数成正比。&基本操作重复执行的次数是问题规模n的某个函数f(n)，于是算法的时间量度可以记为：T(n) = O( f(n) )如果按照这么推断，T(n)应该表示的是算法的时间量度，也就是算法执行的时间。而该页对“语句频度”也有定义：指的是该语句重复执行的次数。如果是基本操作所在语句重复执行的次数，那么就该是f(n)。上边的n都表示的问题规模。以下来自百度知道：对于这些算法(1)
for(i=1;i&=n;i++)for(j=1;j&=n;j++)s++;(2)
for(i=1;i&=n;i++)for(j=i;j&=n;j++)s++;(3)
for(i=1;i&=n;i++)for(j=1;j&=i;j++)s++;(4)
i=1;k=0;while(i&=n-1){k+=10*i;i++;}(5)
for(i=1;i&=n;i++)for(j=1;j&=i;j++)for(k=1;k&=j;k++)x=x+1;对应的时间复杂度为：1.时间复杂度O(n^2)2.时间复杂度O(n^2)3.时间复杂度O(n^2)4.时间复杂度O(n)5.时间复杂度O(n^3)一般来说，时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数)比如：一般总运算次数表达式类似于这样：a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+fa&&0时，时间复杂度就是O(2^n);a=0,b&&0 =&O(n^3);a,b=0,c&&0 =&O(n^2)依此类推那么，总运算次数又是如何计算出的呢？一般来说，我们经常使用for循环，就像刚才五个题，我们就以它们为例1.循环了n*n次，当然是O(n^2)2.循环了(n+n-1+n-2+...+1)≈(n^2)/2，因为时间复杂度是不考虑系数的，所以也是O(n^2)3.循环了(1+2+3+...+n)≈(n^2)/2,当然也是O(n^2)4.循环了n-1≈n次，所以是O(n)5.循环了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6(这个公式要记住哦)≈(n^3)/3，不考虑系数，自然是O(n^3)另外，在时间复杂度中，log(2,n)(以2为底)与lg(n)(以10为底)是等价的，因为对数换底公式：log(a,b)=log(c,b)/log(c,a)所以，log(2,n)=log(2,10)*lg(n),忽略掉系数，二者当然是等价的
还不是太理解
为你推荐：
其他类似问题
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。以下试题来自：
单项选择题算法的时间复杂度是指A) 执行算法程序所需要的时间B) 算法程序的长度C) 算法程序中的指令条数D) 算法执行过程中所需要的基本运算次数
为您推荐的考试题库
你可能感兴趣的试题
1A) sum＜int,4,3＞(5)； B) sum＜4,3＞(5)； C) sum＜int,int,int＞(5)； D) sum(5)；2A) ch＞＝'A' & ch＜＝'Z'B) ch＜＝'A'||ch＞＝'Z'C) 'A'＜＝ch＜＝'Z'D) ch＞＝'A' && ch＜＝'Z'3A) std是一个含有30个元素的对象数组B) std数组中的每个元素都是person类的对象C) std数组中的每个元素都有自己的私有变量num和nameD) std数组中的每个元素都有各自的成员函数init4A) 6 6 B) 5 6C) 1 5 D) 6 55A) 无限次 B) 有语法错，不能执行C) 一次也不执行 D) 执行1次
热门相关试卷
最新相关试卷【图文】时间复杂度的计算_百度文库
您的浏览器Javascript被禁用，需开启后体验完整功能，
享专业文档下载特权
&赠共享文档下载特权
&100W篇文档免费专享
&每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
时间复杂度的计算
阅读已结束，下载本文到电脑
定制HR最喜欢的简历
你可能喜欢算法很重要，但是一般情况下做移动开发并不经常用到，所以很多同学早就将算法打了个大礼包送还给了老师了，况且很多同学并没有学习过算法。这个系列就让对算法头疼的同学能快速的掌握基本的算法。过年放假阶段玩了会游戏NBA2K17的生涯模式，没有比赛的日子也都是训练，而且这些训练都是自发的，没有人逼你，从早上练到晚上，属性也不涨，但是如果日积月累，不训练和训练的人的属性值就会产生较大差距。这个突然让我意识到了现实世界，要想成为一个球星（技术大牛）那就需要日积月累的刻意训练，索性放下游戏，接着写文章吧。
1.算法的效率
虽然计算机能快速的完成运算处理，但实际上，它也需要根据输入数据的大小和算法效率来消耗一定的处理器资源。要想编写出能高效运行的程序，我们就需要考虑到算法的效率。
算法的效率主要由以下两个复杂度来评估：
时间复杂度：评估执行程序所需的时间。可以估算出程序对处理器的使用程度。
空间复杂度：评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。
设计算法时，一般是要先考虑系统环境，然后权衡时间复杂度和空间复杂度，选取一个平衡点。不过，时间复杂度要比空间复杂度更容易产生问题，因此算法研究的主要也是时间复杂度，不特别说明的情况下，复杂度就是指时间复杂度。
2.时间复杂度
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
时间复杂度
前面提到的时间频度T(n)中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律，为此我们引入时间复杂度的概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，它称为算法的渐进时间复杂度，简称时间复杂度。
3.大O表示法
像前面用O( )来体现算法时间复杂度的记法，我们称之为大O表示法。
算法复杂度可以从最理想情况、平均情况和最坏情况三个角度来评估，由于平均情况大多和最坏情况持平，而且评估最坏情况也可以避免后顾之忧，因此一般情况下，我们设计算法时都要直接估算最坏情况的复杂度。
大O表示法O(f(n)中的f(n)的值可以为1、n、logn、n?等，因此我们可以将O(1)、O(n)、O(logn)、O(n?)分别可以称为常数阶、线性阶、对数阶和平方阶，那么如何推导出f(n)的值呢？我们接着来看推导大O阶的方法。
推导大O阶，我们可以按照如下的规则来进行推导，得到的结果就是大O表示法：
1.用常数1来取代运行时间中所有加法常数。
2.修改后的运行次数函数中，只保留最高阶项
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。
先举了例子，如下所示。
int sum = 0,n = 100;
sum = (1+n)*n/2;
System.out.println (sum);
上面算法的运行的次数的函数为f(n)=3，根据推导大O阶的规则1，我们需要将常数3改为1，则这个算法的时间复杂度为O(1)。如果sum = （1+n）*n/2这条语句再执行10遍，因为这与问题大小n的值并没有关系，所以这个算法的时间复杂度仍旧是O(1)，我们可以称之为常数阶。
线性阶主要要分析循环结构的运行情况，如下所示。
for(int i=0;i&n;i++){
//时间复杂度为O(1)的算法
上面算法循环体中的代码执行了n次，因此时间复杂度为O(n)。
接着看如下代码：
int number=1;
while(number&n){
number=number*2;
//时间复杂度为O(1)的算法
可以看出上面的代码，随着number每次乘以2后，都会越来越接近n，当number不小于n时就会退出循环。假设循环的次数为X，则由2^x=n得出x=log?n，因此得出这个算法的时间复杂度为O(logn)。
下面的代码是循环嵌套：
for(int i=0;i&n;i++){
for(int j=0;j&n;i++){
//复杂度为O(1)的算法
内层循环的时间复杂度在讲到线性阶时就已经得知是O(n)，现在经过外层循环n次，那么这段算法的时间复杂度则为O(n?)。
接下来我们来算一下下面算法的时间复杂度：
for(int i=0;i&n;i++){
for(int j=i;j&n;i++){
//复杂度为O(1)的算法
需要注意的是内循环中int j=i，而不是int j=0。当i=0时，内循环执行了n次；i=1时内循环执行了n-1次，当i=n-1时执行了1次，我们可以推算出总的执行次数为：
n+(n-1)+(n-2)+(n-3)+……+1
=(n+1)+[(n-1)+2]+[(n-2)+3]+[(n-3)+4]+……
=(n+1)+(n+1)+(n+1)+(n+1)+……
根据此前讲过的推导大O阶的规则的第二条：只保留最高阶，因此保留n?/2。根据第三条去掉和这个项的常数，则去掉1/2,最终这段代码的时间复杂度为O(n?)。
其他常见复杂度
除了常数阶、线性阶、平方阶、对数阶，还有如下时间复杂度：
f(n)=nlogn时，时间复杂度为O(nlogn)，可以称为nlogn阶。
f(n)=n?时，时间复杂度为O(n?)，可以称为立方阶。
f(n)=2?时，时间复杂度为O(2?)，可以称为指数阶。
f(n)=n!时，时间复杂度为O(n!)，可以称为阶乘阶。
f(n)=(√n时，时间复杂度为O(√n)，可以称为平方根阶。
4.复杂度的比较
下面将算法中常见的f(n)值根据几种典型的数量级来列成一张表，根据这种表，我们来看看各种算法复杂度的差异。
约3.0*10^64
约9.3*10^157
约4.0*10^2567
从上表可以看出，O(n)、O(logn)、O(√n )、O(nlogn )随着n的增加，复杂度提升不大，因此这些复杂度属于效率高的算法，反观O(2?)和O(n!)当n增加到50时，复杂度就突破十位数了，这种效率极差的复杂度最好不要出现在程序中，因此在动手编程时要评估所写算法的最坏情况的复杂度。
下面给出一个更加直观的图：
其中x轴代表n值，y轴代表T(n)值（时间复杂度）。T(n)值随着n的值的变化而变化，其中可以看出O(n!)和O(2?)随着n值的增大，它们的T(n)值上升幅度非常大，而O(logn)、O(n)、O(nlogn)随着n值的增大，T(n)值上升幅度则很小。
常用的时间复杂度按照耗费的时间从小到大依次是：
O(1)&O(logn)&O(n)&O(nlogn)&O(n?)&O(n?)&O(2?)&O(n!)
《大话数据结构》
《挑战程序设计竞赛2》
欢迎关注我的微信公众号，第一时间获得博客更新提醒，以及更多成体系的Android相关原创技术干货。
扫一扫下方二维码即可关注：
时间复杂度和空间复杂度详解
常见排序算法及对应的时间复杂度和空间复杂度
时间复杂度和空间复杂度
时间复杂度和空间复杂度的简单讲解
如何计算时间复杂度
关于计算时间复杂度和空间复杂度
算法基础（二）——算法时间复杂度和渐进时间复杂度
算法时间复杂度计算方法
什么是算法的复杂度？
没有更多推荐了，
独立博客：
qq交流群：
不仅分享Android、Java和移动前端相关技术，还有行业动态、技术资讯、面经和个人感悟。每个月都会争取送书福利给大家。
实力博主Tamic：&>&时间复杂度的几种计算方法
时间复杂度的几种计算方法
上传大小：247KB
算法的时间复杂度是反映算法优劣的重要指标是数 据 结 构的 重 要 理 论 基 础是学习和教学过程中贯穿始终的主要线索
几种常用的时间复杂度计算方法使对该知识点的教学和学习变得系统和简单
综合评分：5
10积分/C币
{%username%}回复{%com_username%}{%time%}\
/*点击出现回复框*/
$(".respond_btn").on("click", function (e) {
$(this).parents(".rightLi").children(".respond_box").show();
e.stopPropagation();
$(".cancel_res").on("click", function (e) {
$(this).parents(".res_b").siblings(".res_area").val("");
$(this).parents(".respond_box").hide();
e.stopPropagation();
/*删除评论*/
$(".del_comment_c").on("click", function (e) {
var id = $(e.target).attr("id");
$.getJSON('/index.php/comment/do_invalid/' + id,
function (data) {
if (data.succ == 1) {
$(e.target).parents(".conLi").remove();
alert(data.msg);
$(".res_btn").click(function (e) {
var parentWrap = $(this).parents(".respond_box"),
q = parentWrap.find(".form1").serializeArray(),
resStr = $.trim(parentWrap.find(".res_area_r").val());
console.log(q);
//var res_area_r = $.trim($(".res_area_r").val());
if (resStr == '') {
$(".res_text").css({color: "red"});
$.post("/index.php/comment/do_comment_reply/", q,
function (data) {
if (data.succ == 1) {
var $target,
evt = e || window.
$target = $(evt.target || evt.srcElement);
var $dd = $target.parents('dd');
var $wrapReply = $dd.find('.respond_box');
console.log($wrapReply);
//var mess = $(".res_area_r").val();
var mess = resS
var str = str.replace(/{%header%}/g, data.header)
.replace(/{%href%}/g, 'http://' + window.location.host + '/user/' + data.username)
.replace(/{%username%}/g, data.username)
.replace(/{%com_username%}/g, data.com_username)
.replace(/{%time%}/g, data.time)
.replace(/{%id%}/g, data.id)
.replace(/{%mess%}/g, mess);
$dd.after(str);
$(".respond_box").hide();
$(".res_area_r").val("");
$(".res_area").val("");
$wrapReply.hide();
alert(data.msg);
}, "json");
/*删除回复*/
$(".rightLi").on("click", '.del_comment_r', function (e) {
var id = $(e.target).attr("id");
$.getJSON('/index.php/comment/do_comment_del/' + id,
function (data) {
if (data.succ == 1) {
$(e.target).parent().parent().parent().parent().parent().remove();
$(e.target).parents('.res_list').remove()
alert(data.msg);
//填充回复
function KeyP(v) {
var parentWrap = $(v).parents(".respond_box");
parentWrap.find(".res_area_r").val($.trim(parentWrap.find(".res_area").val()));
评论共有1条
很不错的资源
VIP会员动态
CSDN下载频道资源及相关规则调整公告V11.10
下载频道用户反馈专区
下载频道积分规则调整V1710.18
spring mvc+mybatis+mysql+maven+bootstrap 整合实现增删查改简单实例.zip
资源所需积分/C币
当前拥有积分
当前拥有C币
输入下载码
为了良好体验，不建议使用迅雷下载
时间复杂度的几种计算方法
会员到期时间：
剩余下载个数：
剩余积分：0
为了良好体验，不建议使用迅雷下载
积分不足！
资源所需积分/C币
当前拥有积分
您可以选择
程序员的必选
绿色安全资源
资源所需积分/C币
当前拥有积分
当前拥有C币
为了良好体验，不建议使用迅雷下载
资源所需积分/C币
当前拥有积分
当前拥有C币
为了良好体验，不建议使用迅雷下载
资源所需积分/C币
当前拥有积分
当前拥有C币
您的积分不足，将扣除 10 C币
为了良好体验，不建议使用迅雷下载
无法举报自己的资源
你当前的下载分为234。
你还不是VIP会员
开通VIP会员权限，免积分下载
你下载资源过于频繁，请输入验证码
您因违反CSDN下载频道规则而被锁定帐户，如有疑问，请联络:!
若举报审核通过，可返还被扣除的积分
被举报人：
请选择类型
资源无法下载 （ 404页面、下载失败、资源本身问题）
资源无法使用 （文件损坏、内容缺失、题文不符）
侵犯版权资源 （侵犯公司或个人版权）
虚假资源 （恶意欺诈、刷分资源）
含色情、危害国家安全内容
含广告、木马病毒资源
*投诉人姓名：
*投诉人联系方式：
*版权证明：
*详细原因：
时间复杂度的几种计算方法}