`
endual
  • 浏览: 3566333 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

求解算法的时间复杂度的具体步骤

 
阅读更多
求解算法的时间复杂度的具体步骤

求解算法的时间复杂度的具体步骤是:

  ⑴ 找出算法中的基本语句;

  算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。

  ⑵ 计算基本语句的执行次数的数量级;

  只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。

  ⑶ 用大Ο记号表示算法的时间性能。

  将基本语句执行次数的数量级放入大Ο记号中。

  如果算法中包含嵌套的循环,则基本语句通常是最内层的循环体,如果算法中包含并列的循环,则将并列循环的时间复杂度相加。例如:

  for (i=1; i<=n; i++)
  x++;

  for (i=1; i<=n; i++)
  for (j=1; j<=n; j++)
  x++;

  第一个for循环的时间复杂度为Ο(n),第二个for循环的时间复杂度为Ο(n2),则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。

  常见的算法时间复杂度由小到大依次为:

  Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)

  Ο(1)表示基本语句的执行次数是一个常数,一般来说,只要算法中不存在循环语句,其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间,而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法,把这类问题称为P类问题,而把后者称为NP问题。

O(1)

Temp=i;i=j;j=temp;                    

以上三条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶,记作T(n)=O(1)。如果算法的执行时 间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

O(n^2)

2.1. 交换i和j的内容
     sum=0;                 (一次)
     for(i=1;i<=n;i++)       (n次 )
        for(j=1;j<=n;j++) (n^2次 )
         sum++;       (n^2次 )
解:T(n)=2n^2+n+1 =O(n^2)

2.2.   
    for (i=1;i<n;i++)
    {
        y=y+1;         ①   
        for (j=0;j<=(2*n);j++)    
           x++;        ②      
    }         
解: 语句1的频度是n-1
          语句2的频度是(n-1)*(2n+1)=2n^2-n-1
          f(n)=2n^2-n-1+(n-1)=2n^2-2
          该程序的时间复杂度T(n)=O(n^2).         

O(n)      
                                                      
2.3.
    a=0;
    b=1;                      ①
    for (i=1;i<=n;i++) ②
    {  
       s=a+b;    ③
       b=a;     ④  
       a=s;     ⑤
    }
解: 语句1的频度:2,        
           语句2的频度: n,        
          语句3的频度: n-1,        
          语句4的频度:n-1,    
          语句5的频度:n-1,                                  
          T(n)=2+n+3(n-1)=4n-1=O(n).
                                                                                                 
O(logn )

2.4.
     i=1;       ①
    while (i<=n)
       i=i*2; ②
解: 语句1的频度是1,  
          设语句2的频度是f(n),   则:2^f(n)<=n;f(n)<=logn    
          取最大值f(n)= logn,
          T(n)=O(logn )

O(n^3)

2.5.
    for(i=0;i<n;i++)
    {  
       for(j=0;j<i;j++)  
       {
          for(k=0;k<j;k++)
             x=x+2;  
       }
    }
解:当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).

分享到:
评论

相关推荐

    算法时间复杂度

    根据给定文件的信息,我们可以详细地探讨“算法时间复杂度”的相关知识点。时间复杂度是衡量算法运行时间随输入规模增长而变化的函数,它在计算机科学与编程领域扮演着至关重要的角色。接下来,我们将围绕以下几个...

    算法时间复杂度分析中递归方程求解方法综述

    ### 算法时间复杂度分析中递归方程求解方法综述 #### 引言 在计算机科学领域,递归是一种常见的编程思想和技术,它不仅被广泛应用于各种算法的设计之中,也是评估算法效率的重要工具之一。递归方程在算法的时间...

    广度优先搜索构建迷宫(BFS算法)动态构建过程_深度优先算法时间复杂度

    在时间复杂度方面,BFS和DFS都是O(V+E),其中V是节点数量,E是边的数量。这是因为这两种算法都需要遍历所有的节点和边。然而,实际运行效率上,由于BFS使用队列,通常比DFS(使用栈)更稳定,因为DFS可能会陷入深度...

    算法时间复杂度的计算.doc

    本文档主要介绍了如何计算算法的时间复杂度,并通过一个具体的例子进行了详细的解析。 首先,时间复杂度的定义是基于算法中基本操作的执行次数与问题规模 n 的关系。基本操作是指算法中执行频率最高的那些语句。当 ...

    《算法与数据结构》笔记—算法及时间复杂度

    最坏情况下的时间复杂度是指算法求解输入规模为 n 的实例所需要的最长时间。平均情况下的时间复杂度是指算法对同样规模 n 的输入实例所需要的平均时间。 算法的基本运算是指算法中最基本的操作,例如比较、加法、...

    Algorithm And Complexity 《算法和复杂度》(英文版)

    ### 知识点总结:《算法与复杂度...通过上述章节和核心概念的介绍,《算法与复杂度》不仅为读者提供了算法设计的基础知识,还深入探讨了算法的复杂度评估及其在具体问题中的应用,是一本非常有价值的计算机科学参考书。

    概率算法--降低算法的复杂度

    ### 概率算法——降低算法复杂度 #### 一、概率算法的概念与优势 概率算法是一种在执行过程中引入随机性的算法。与确定性算法不同,概率算法中的某些步骤是不确定的,即它们依赖于随机选择。这种随机选择往往能够...

    具有O(n)时间复杂度的分布式请求集生成算法.pdf

    通过引入二次松弛差集和优化求解步骤,它显著降低了算法的复杂度,提升了系统的并发性能。对于从事分布式系统开发的工程师和研究人员来说,这是一份有价值的参考文献,可以指导他们在设计和实现分布式系统时,如何...

    分治法与时间复杂度计算

    时间复杂度是衡量算法效率的一种方式,它描述了算法运行时间与输入数据量之间的关系。主要关注最坏情况下的时间复杂度,因为它给出了算法性能的上限。大O符号(O)用来表示算法运行时间的增长速率。 **常见的时间...

    04-时间复杂度的求解方法.pptx

    时间复杂度的求解方法通常包括以下几个步骤: 1. **分析算法**:仔细观察算法的每一步,确定每一步与输入数据 n 的关系。 2. **计数操作次数**:统计在最坏情况下,算法会执行的基本操作次数。 3. **忽略低阶项和...

    第一章-算法概述-1.pdf

    - **有限性**: 算法的步骤数量是有限的,并且每个步骤的执行时间也有限。 此外,还对比了**程序**与**算法**之间的区别:程序是对算法的一种具体实现,它可以通过某种编程语言来编写。值得注意的是,程序并不一定...

    基于二分排序法时间复杂度的求解过程.pdf

    本文将基于二分排序法时间复杂度的求解过程进行深入探讨,分析该算法在不同场景下的性能表现,并通过实际代码展示其具体实现。 在进行算法分析时,时间复杂度是一个不可或缺的概念。它反映了算法执行时间与输入数据...

    算法设计与分析本科实验报告(Python).doc

    3. 分治策略:掌握分治法的设计思想、求解步骤、掌握用分治法解题的算法框架。 4. matplotlib 模块:使用 matplotlib 模块画出操作时间和数据规模的关系图。 5. turtle 模块:使用 turtle 模块实现递归可视化。 ...

    cvxmatlab算法包

    这些函数包括但不限于问题的建模、求解器的选择、问题的求解以及结果的后处理等步骤。CVX支持多种求解器,如MOSEK、SDPT3等,可以根据问题的类型和规模自动选择最合适的求解策略。 使用CVX时,你需要遵循一定的规则...

    MasterMind问题求解算法分析与改进.pdf

    文档首先提出了一种精简版算法,该算法通过减少计算过程中的重复步骤和优化逻辑判断流程,显著降低了时间复杂度。虽然它在某些情况下略微增加了猜测次数,但总体上通过优化算法设计,减少了总体的计算负担。 为了更...

    区间并集求解算法java实现

    区间并集求解算法java实现 区间并集求解算法是解决有限闭区间的并集问题,这是计算机科学和数学领域的重要问题。在实际应用中,例如邮政发票系统中,需要计算用户共打印了多少条发票,这可以抽象为数学上计算区间的...

    俄式乘法_俄式乘法_

    在分析时间复杂度时,我们可以看到,无论是递归还是非递归算法,俄式乘法的时间复杂度都是O(n),其中n为输入数字的位数。这是因为每一步都需要处理n位数字。这比传统的乘法算法(如学校教的竖式乘法)的O(n^2)时间...

    蜣螂优化算法 (DBO).rar

    在压缩包文件中,“蜣螂优化算法.pdf”很可能是一篇详细描述该算法原理、实现方法以及应用案例的研究论文,可以帮助读者深入理解算法的细节和应用。而“发行版”可能包含了算法的源代码或者软件包,可供研究者和...

Global site tag (gtag.js) - Google Analytics