首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法中的时间复杂度

算法中的时间复杂度

作者头像
张云飞Vir
发布2020-03-23 16:03:06
1.1K0
发布2020-03-23 16:03:06
举报
文章被收录于专栏:写代码和思考写代码和思考

概述

程序员写代码过程中总要用到算法,而不同的算法有不同的效率,时间复杂度是用来评估的算法的效率的一种方式。

比如说对于一个功能,可以实现的方法很多种,我们在实现过程中选择效率最佳的方式来实现,它影响了我们在一定的场景下选择的数据结构和算法,比如何时选择使用ArrayList,何时用LinkedList。

本文结构:

概念
    渐进时间复杂度
场景示例
    场景1
    场景2
    场景3
    场景4
推导出时间复杂度
     时间复杂度计算方式
     常数阶
     线性阶
     平方阶
     立方阶
     对数阶

概念

在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。 时间复杂度常用大O符号表述。 时间复杂度可被称为是渐近的,即考察输入值大小趋近无穷时的情况。

简单理解就是:

  • 用 “大O” 表示 “时间复杂度”,示例: O(n)
  • 用一个函数表达算法复杂度的值,格式:O( 具体不同的函数 )
  • 它定性的描述“运行时间”
  • 它是渐进的,趋向接近的。

渐进时间复杂度

为便于计算时间复杂度,通常会估计算法的操作单元数量,每个单元运行的时间都是相同的。因此,总运行时间和算法的操作单元数量最多相差一个常量系数。

简化的公式表示: 总运行时间 = 操作次数 * 固定时间的运行单元

而算法有很多种,很难直接比较。我们期望“操作次数”是一个常数,而实际它很难直接用常数表示。于是引入了 渐进时间复杂度,官方的定义如下:

渐进时间复杂度(asymptotic time complexity): 若存在函数 f(n),使得当n趋近于无穷大时,T(n)/ f(n)的极限值为不等于零的常数,则称 f(n)是T(n)的同数量级函数。记作 T(n)= O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

渐进时间复杂度用大写O来表示,所以也被称为大O表示法

场景示例

场景1:

一条长16寸的面包,每1天16寸,需要多少天呢?

太简单了,一天。 函数表示: T(n) = 1

场景2:

一条长16寸的面包,每5天吃掉面包剩余长度的一半,那么把面包吃得只剩下1寸,需要多少天呢?

就是数字16不断地除以2,直到等于1?这里要涉及到数学当中的对数,以2位底,16的对数,可以简写为log16。因此,需要 5 X log16 = 5 X 4 = 20 天。 函数表示: T(n) = 5logn。

场景3:

一条长10寸的面包,每3天吃掉1寸,那么吃掉整个面包需要几天?

很简单,即 函数表示: T(n) = 3n。

场景4:

一条长10寸的面包,吃掉第一个一寸需要1天时间,吃掉第二个一寸需要2天时间,吃掉第三个一寸需要3天时间.....每多吃一寸,所花的时间也多一天。那么小吃掉整个面包需要多少天呢?

答案是从1累加到10的总和,也就是55天。即 1+2+3+......+ n-1 + n = (1+n)*n/2 = 0.5n^2 + 0.5n。 函数表示: T(n) = 0.5n^2 + 0.5n。

推导出时间复杂度

推导出时间复杂度呢?有如下几个原则:

(1) 如果运行时间是常数量级,用常数1表示; (2) 只保留时间函数中的最高阶项; (3) 如果最高阶项存在,则省去最高阶项前面的系数。

场景1: T(n) = 1 最高阶项为3n,省去系数3,转化后为:T(n) = O(1)

场景2: T(n) = 5logn 最高阶项为5logn,省去系数5,转化后为:T(n) = O(logn)

场景3: T(n) = 3n 最高阶项为3n,省去系数3,转化后为:T(n) = O(n)

场景4: T(n) = 0.5n^2 + 0.5n 最高阶项为0.5n^2,省去系数0.5,转化后为:T(n) = O(n^2) 备注:^ 符号表示 平方,n^2表示 n的平方

这四种时间复杂度究竟谁用时更长,谁节省时间呢?稍微思考一下就可以得出结论:

O(1)< O(logn)< O(n)< O(n^2)

其实这四种对应的时间复杂度是: 常数阶,对数阶,线性阶,立方阶。

常见时间复杂度还有:常数阶、线性阶、平方阶、立方阶、对数阶、nlog2n阶、指数阶 效率:O(1) > O(log2n)> o(n)> o(nlog2n) > o(n^2) > o(n^3) > o(2^n) > o(n!) > o(n^n)

代码中的时间复杂度

时间复杂度计算方式

举例:计算1+2+3+....+n的和

$sum=0

for($i=1;$i<=$n;$i++){
   $sum+=$i
}

可以看到循环了n次,所以时间复杂度就是O(n)

常数阶 O(1)

function test($n){
    echo $n;
    echo $n;
    echo $n;
}

执行了三次 echo,运行次数很固定,是个常数。那么时间复杂度就是O(3),取为O(1)

线性阶 O(n)

for($i=1;$i<=$n;$i++){
    $sum+=$i
}

执行n 次,时间复杂度就是O(n)

平方阶:o(n2)/o(n3)

$sum=0;
for($i=1;$i<=$n;$i++){
    for($j=1;$j<$n;$j++){
    $sum+=$j
    }
}

两次循环,里面循环执行了n次,外层循环也执行了n次,所以时间复杂度为O(n^2)

立方阶

与上面类似,就是 三个 for 循环

对数阶:O(log2n)

while($n>=1){
    $n=$n/2;
}

即不断除以2,

n          n/2        n/2/2      n/2/2/2    n/2/2/...

规律:n/(2^m)=1;我们需要算出m, 转换成n=2^m,得出m=log2n,所以时间复杂度为O(logn)

END

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 概述
  • 概念
  • 渐进时间复杂度
  • 场景示例
    • 场景1:
      • 场景2:
        • 场景3:
        • 场景4:
        • 推导出时间复杂度
    • 代码中的时间复杂度
      • 时间复杂度计算方式
        • 常数阶 O(1)
          • 线性阶 O(n)
            • 平方阶:o(n2)/o(n3)
              • 立方阶
                • 对数阶:O(log2n)
                领券
                问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档