QQ登录

只需一步,快速开始

登录 | 立即注册 | 找回密码

主题

帖子

荣誉

新鱼友

Rank: 1

积分
55
查看: 200|回复: 0

[学习笔记] 数据结构(三)时间复杂度与大O阶

[复制链接]
最佳答案
0 
累计签到:21 天
连续签到:1 天
sdsd 发表于 2017-8-12 19:14:35 2000 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

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

x

本学习笔记由《大话数据结构》第二章学习整理而来,本学习笔记里涉及的程序是基于C语言的


运行时间是度量时间复杂度的指标,而测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数,运行时间与这个计数成正比。算法时间复杂度的定义:在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况,并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)=O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。

这样用大写O()来体现算法时间复杂度的记法,我们称之为大O记法。例如O(n),O(1)。

下面给出分析一个算法时间复杂度大O阶的方法:
推导大O阶:
1.计算出此算法总共的操作执行次数T(n)。
2.用常数1取代运行时间中的所有加法常数。
3.在修改后的运行次数函数中,只保留最高阶项。
4.如果最高阶项存在且不是1,则去除与这个项相乘的常数。
得到的结果就是大O阶。

是不是觉得上面的方法有点抽象呢,下面我们开始举几个例子
一、常数阶O(1)

  1. int sum=0,n=100;   /*执行一次*/
  2. sum=(1+n)*n/2;     /*执行一次*/
  3. printf("%d",sum);   /*执行一次*/
复制代码
这个算法的操作次数T(n)=3,根据前面的推导大O阶的方法,将3改成1,在保留最高项时,发现其没有最高项。因此这个算法的时间复杂度为O(1)。
对于单纯的分支结构(不含循环结构)而言,执行次数都是恒定的,不随n的变化而变化,其时间复杂度都是O(1)。
二、线性阶O(n)
线性阶的循环结构要复杂一点,要分析算法的复杂度,关键就是要分析循环结构的运行情况。
  1. int i;  /*执行一次*/
  2. for(i=0;i<n;i++) /*执行n+1次*/
  3. {
  4.       sum+=i;  /*执行n次
  5. }
复制代码
此算法的T(n)=2n+2,根据前面的推导大O阶的方法,可以求出时间复杂度为O(n)
三、对数阶O(logn)
代码如下
  1. int count=1;
  2. while(count<n)
  3. {
  4.      count=count*2;
  5. }
复制代码
有多少个2相乘后大于n,则会退出循环。由2的x次方为n可以得到x=logn。所以这个循环的时间复杂度为O(logn)
四、平方阶O(logn)
  1. int i,j;  /*执行一次*/
  2. for(i=0;i<n;i++) /*执行n+1次*/
  3. {
  4.      for(j=0;j<n;j++)/*执行n*(n+1)次*/
  5.     {
  6.         sum=sum+i+j;  /*执行n*n次*/
  7.     }      
  8. }
复制代码
外层循环执行一次,内部循环执行n次,外层需要执行n次,所以内部循环总共执行n*n次。T(n)=1+n+1+n*(n+1)+n*n,,根据前面的推导大O阶的方法,可以求出时间复杂度为O(n^2)

常见的时间复杂度
执行次数函数非正式术语
12O(1) 常数阶
2n+3O(n)线性阶
3n^2+2n+1O(n^2)平方阶
5logn+20O(logn)对数阶
2n+3nlogn+19O(nlogn) nlogn阶
6n^3+2n^2+4O(n^3) 立方阶
2^nO(2^n) 指数阶


常用的时间复杂度耗费时间从小到大的顺序是:
O(1) <O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3) <O(2^n)<O(n!)<O(n^n)

评分

参与人数 1鱼币 +10 收起 理由
小甲鱼 + 10

查看全部评分

楼层
跳转到指定楼层

发表回复

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

本版积分规则

关闭

小甲鱼强烈推荐 上一条 /1 下一条

    移动客户端下载(未启用)
    微信公众号

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备11014136号

Copyright 2018 鱼C论坛 版权所有 All Rights Reserved.

Powered by Discuz! X3.1 Copyright
© 2001-2018 Comsenz Inc.    All Rights Reserved.

小黑屋|手机版|Archiver|鱼C工作室 ( 粤公网安备 44051102000370号 | 粤ICP备11014136号

GMT+8, 2017-12-19 06:18

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