【算法与数据结构】关于代码运行时间复杂度的计算方法-阿里云开发者社区

开发者社区> 傲海> 正文

【算法与数据结构】关于代码运行时间复杂度的计算方法

简介: (转载请注明出处:http://blog.csdn.net/buptgshengod) 1.背景知识        大O标记就不用我说了吧。O(n)这种时间复杂度的意义自己google吧。这里简单讲下从代码推算。 2.具体案例  (1)案例一   int a=0; //第一行 for(int i=0;i<=N;i++)//第二行
+关注继续查看

(转载请注明出处:http://blog.csdn.net/buptgshengod

1.背景知识

       大O标记就不用我说了吧。O(n)这种时间复杂度的意义自己google吧。这里简单讲下从代码推算。

2.具体案例

 (1)案例一

  
int a=0;                      //第一行
for(int i=0;i<=N;i++)//第二行
{
  a+=i*i*i;                  //第三行
}
我们来看下。
第一行,声明变量并赋值用一个时间单元;
第二行,首先给i赋值,一个时间单元。i<=N是N+1个时间单元。i++是N个时间单元。第二行总共2N+2个时间单元。
第三行,一个加法,一个赋值,两个乘法,一共四个时间单元。执行N次,一共4N个时间单元。

所以这段代码一共6N+3个时间单元。时间复杂度为O(N);

(2)案例二

   一个for循环
for(int i=0;i<=N;i++)
时间复杂度O(n)

 
  嵌套for循环
for(i=0;i<n;i++)
{
   for(j=0;j<n;j++)
 {}
}
时间复杂度O(n²)


 三层嵌套语句
for(m=0;m<n;m++)
{
    int a=0;
    for(i=0;i<n;i++)
   {
       for(j=0;j<n;j++)
      {}
    }
}
时间复杂度为O(n³)。

if/else语句
时间复杂度,是if和else中最长的那个。


简单的递归函数如
public static int test(int n)
{
     if(n<=1)
      {
         return 1;
       }
     else
       {
        return n*test(n-1);
       }
}
相当与一个for的循环,时间复杂的是O(n)


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
排序算法大数据量测试代码
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; using System.Diagnostics; using System.IO; namespace Sort { class Program
829 0
冰与火之歌:「时间」与「空间」复杂度 | 算法必看系列三十六
对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间; 反之,求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。
2254 0
javascript 一个关于时间排序的算法(一个页面多个倒计时排序)
上周要做一个活动页面 秒杀列表页 需要一个时间的算法排序 自己琢磨了半天想了各种算法也没搞出来,后来问了下一个后台的php同学 他写了个算法给我看了下 ,刚开始看的时候觉得这就是个纯算法,不能转化成页面的dom效果,可是再看了两遍发现可以 于是我就改了改 实现了 不禁感叹 确实蛮赞的 于是就博一客;...
852 0
Python之数据聚合与分组运算
Python之数据聚合与分组运算 1. 关系型数据库方便对数据进行连接、过滤、转换和聚合。 2. Hadley Wickham创建了用于表示分组运算术语“split-apply-combine”(拆分-应用-合并)。 3. GroupBy的size方法,它可以返回一个含有分组大小的Series。 4. gorupby对分组进行迭代,可以产生一组二元元组
1547 0
机密计算: 一种基于硬件的、服务于应用和数据的可信执行计算形态
注:本文是对[机密计算联盟](https://confidentialcomputing.io/)发布的白皮书[Confidential Computing: Hardware-Based Trusted Execution for Applications and Data v1.2](https://confidentialcomputing.io/wp-content/uploads/sit
544 0
+关注
傲海
著有《机器学习实践应用》,阿里云机器学习PAI产品经理,个人微信公众号&ldquo;凡人机器学习&rdquo;。
302
文章
10
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载