`
geeksun
  • 浏览: 965316 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

算法复杂度

阅读更多

        算法的复杂度分为时间复杂度和空间复杂度,时间复杂度是算法执行时间的多少,空间复杂度是算法占用空间的大小。

1. 时间复杂度:

1.1 时间频度

一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

1.2. 分类

  常见的时间复杂度,按数量级递增排列,有:

  常数阶O(1),对数阶O(log2n),线性阶O(n),

  线性对数阶O(nlog2n),平方阶O(n^2),立方阶O(n^3),...,

  k次方阶O(n^k), 指数阶O(2^n) 。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

如果算法中语句执行次数为常数,那么时间复杂度为O(1)。

2. 空间复杂度:

空间复杂度(Space Complexity)是一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地\"进行的,是节省存储的算法;有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,如快速排序和归并排序算法就属于这种情况。

如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为0(log2n);当一个算法的空间复杂度与n成线性比例关系时,可表示为0(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。 

附:常见的算法的时间复杂度和空间复杂度

  • 大小: 40.5 KB
分享到:
评论

相关推荐

    关于算法复杂度的概念的PPT

    在这里,我们将从算法复杂度的概念开始,讨论算法复杂度的定义、描述增长趋势的方法、算法复杂度的考察方法、算法复杂度的上界和下界、Fibonacci 数列问题的解决方法等。 首先,算法复杂度是指问题随规模的增长算法...

    算法复杂度分析ppt

    算法复杂度分析算法复杂度分析算法复杂度分析算法复杂度分析算法复杂度分析算法复杂度分析

    算法复杂度速查表

    程序员应该掌握的算法复杂度速查表 这个总结非常方便 不仅形象地把各个算法对比开来 也特别利于面试前的复习。

    算法复杂度计算方法

    ### 算法复杂度计算方法 #### 一、时间复杂度 时间复杂度是用来评估算法执行速度的一个重要指标,通常用于衡量算法随输入数据规模(通常标记为n)的增长趋势。 ##### 1. 时间频度 - **定义**:算法执行过程中基本...

    算法复杂度O(mn)的均值滤波

    #### 四、算法复杂度分析 经过优化后,对于每个像素点,只需要执行一次加法和一次减法操作即可完成均值的计算。因此,整个算法的计算复杂度为 O(mn)。相较于传统方法,该算法大大降低了计算量,提高了效率。 #### ...

    算法复杂度原理

    算法复杂度是衡量一个算法效率的重要指标,它主要关注在最坏、最好和平均情况下,算法执行时间或空间需求的增长趋势。理解算法复杂度对于优化程序性能和选择合适的算法至关重要。初学者在学习这一概念时,应从以下几...

    算法复杂度分析基础课件

    《算法复杂度分析基础》 算法复杂度分析是评估算法效率的重要工具,主要涉及时间复杂度和空间复杂度两个方面。这门基础课程旨在教授如何分析算法在处理大规模数据时所需的资源,帮助开发者优化程序性能。 一、算法...

    数据结构算法复杂度题目答案

    在计算机科学中,数据结构和算法的复杂度分析是至关重要的,因为它可以帮助我们评估程序的效率,预测其在大规模数据下的表现。以下是给定题目中涉及的一些知识点。 1. 大O符号(Big-Oh)表示法:大O符号是用来描述...

    大O表示法与算法复杂度分析:深入理解与应用指南

    大O表示法是一种用于描述算法复杂度的数学符号,它可以帮助我们理解和比较不同算法的效率。本文将详细介绍大O表示法的基本概念、分类、以及如何使用它来分析和描述算法的复杂度。 大O表示法是理解和分析算法复杂度的...

    算法复杂度作业2

    在IT领域,算法复杂度是衡量程序效率的重要标准,它主要关注的是算法在处理数据时所需的时间和空间资源。在“算法复杂度作业2”中,我们可能涉及到多个编程语言和工具,如Shell、Perl、sed、awk以及Java,它们在解决...

    探索AI画布背后的奥秘:AI绘画软件算法复杂度解析

    ### 探索 AI 画布背后的奥秘:AI 绘画软件算法复杂度解析 AI绘画,作为一种新兴的艺术创作方式,正逐步改变着我们对视觉艺术的理解与体验。这一技术的发展,离不开深度学习领域的进步,尤其是生成对抗网络(GANs)...

    C++矩阵连乘源代码和题目描述和算法复杂度的解析

    本文将深入探讨C++实现矩阵连乘的源代码、题目描述、以及算法复杂度的解析。 首先,我们要理解矩阵连乘的基本概念。在数学中,矩阵连乘是指对两个或多个矩阵进行乘法操作。对于给定的矩阵A和B,它们可以相乘的前提...

    dft和fft算法复杂度比较

    用matlab实现dft和fft算法复杂度比较

    每个程序员都应该收藏的算法复杂度速查表 – 码农网1

    算法复杂度速查表 本文旨在为程序员提供一个算法复杂度速查表,涵盖计算机科学中常见算法的时间和空间复杂度。该速查表可以帮助程序员在面试和编程中快速查找算法的复杂度,从而节省时间和提高效率。 数据结构操作...

    StrongPosHao#LearningProcessRecord#排序算法复杂度总结1

    排序算法复杂度总结

    最大公约数的三种算法复杂度分析时间计算.pdf

    《最大公约数的三种算法复杂度分析》 在计算机科学中,算法的效率是衡量其性能的重要指标,特别是在处理大量数据时。本文将详细探讨求两个自然数最大公约数(Greatest Common Divisor, GCD)的三种常见算法:连续...

    由数据范围反推算法复杂度以及算法内容

    ### 由数据范围反推算法复杂度及其应用 在计算机科学与编程竞赛中,了解算法的时间复杂度对于选择合适的算法解决特定问题至关重要。通过题目给出的数据规模(即输入数据的大小),我们可以反向推导出适合该问题的...

    算法复杂度——时间复杂度和空间复杂度.doc

    ### 算法复杂度详解:时间复杂度与空间复杂度 #### 一、时间复杂度 **1. 时间频度** 在讨论算法效率时,我们通常关注算法执行所耗费的时间。理论上直接计算出算法的确切执行时间是不可行的,这需要具体的硬件...

    最大公约数的三种算法复杂度分析时间计算.doc

    最大公约数的三种算法复杂度分析时间计算.doc

Global site tag (gtag.js) - Google Analytics