精华内容
下载资源
问答
  • 高级工程师title我,最近琢磨着好好刷刷算法题更高级一些,然鹅,当我准备回忆大学和面试时候学数据结构之时,我发现自己对这个算法复杂度的记忆只有OOOOOooo算法(Algorithm)是指用来操作数据、解决程序问题的一...

    高级工程师title的我,最近琢磨着好好刷刷算法题更高级一些,然鹅,当我准备回忆大学和面试时候学的数据结构之时,我发现自己对这个算法复杂度的记忆只有OOOOOooo

    算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别。

    那么我们应该如何去衡量不同算法之间的优劣呢?

    主要还是从算法所占用的「时间」和「空间」两个维度去考量。

    • 时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。
    • 空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。

    因此,评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而,有的时候时间和空间却又是「鱼和熊掌」,不可兼得的,那么我们就需要从中去取一个平衡点。

    时间复杂度

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

    时间频度T(n)中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律,为此我们引入时间复杂度的概念。算法的时间复杂度也就是算法的时间度量,记作:T(n) = O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称「时间复杂度」。

    这种表示方法我们称为「 大O符号表示法 」,又称为渐进符号,是用于描述函数渐进行为的数学符号

    常见的时间复杂度量级有:

    • 常数阶
    • 线性阶
    • 平方阶
    • 立方阶
    • 对数阶
    • 线性对数阶
    • 指数阶

    常数阶

    ,表示该算法的执行时间(或执行时占用空间)总是为一个常量,不论输入的数据集是大是小,只要是没有循环等复杂结构,那这个代码的时间复杂度就都是O(1),如:

    int i = 1;int j = 2;int k = i + j;

    上述代码在执行的时候,它消耗的时候并不随着某个变量的增长而增长,那么无论这类代码有多长,即使有几万几十万行,都可以用来表示它的时间复杂度。

    线性阶

    ,表示一个算法的性能会随着输入数据的大小变化而线性变化,如

    for (int i = 0; i < n; i++) { j = i;   j++;}

    这段代码,for循环里面的代码会执行n遍,因此它消耗的时间是随着n的变化而变化的,因此这类代码都可以用来表示它的时间复杂度。

    平方阶

    ² 表示一个算法的性能将会随着输入数据的增长而呈现出二次增长。最常见的就是对输入数据进行嵌套循环。如果嵌套层级不断深入的话,算法的性能将会变为立方阶,,以此类推

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

    指数阶

    ,表示一个算法的性能会随着输入数据的每次增加而增大两倍,典型的方法就是裴波那契数列的递归计算实现

    int Fibonacci(int number){    if (number <= 1) return number;    return Fibonacci(number - 2) + Fibonacci(number - 1);}

    对数阶

    int i = 1;while(i

    上面的代码,在while循环里面,每次都将 i 乘以 2,乘完之后,i 距离 n 就越来越近了,直到i不小于n退出。我们试着求解一下,假设循环次数为x,也就是说 2 的 x 次方等于 n,则由2^x=n得出x=log₂n。因此这个代码的时间复杂度为

    线性对数阶

    线性对数阶,就是将时间复杂度为对数阶的代码循环n遍的话,那么它的时间复杂度就是 n * O(logN),也就是了,如下,

    for(m=1; m

    除此之外,其实还有平均情况复杂度、最好时间复杂度、最坏时间复杂度。。。一般没有特殊说明的情况下,都是值最坏时间复杂度。


    空间复杂度

    空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势,一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)),其中n为问题的规模,S(n)表示空间复杂度。

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

    一般情况下,一个程序在机器上执行时,除了需要存储程序本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身,和算法无关,这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数,则称此算法为原地工作,空间复杂度为O(1)。当一个算法的空间复杂度与n成线性比例关系时,可表示为,类比时间复杂度。

    空间复杂度比较常用的有:O(1)、O(n)、O(n²)

    空间复杂度

    如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1) 举例:

    int i = 1;int j = 2;++i;j++;int m = i + j;

    代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)

    空间复杂度

    int[] m = new int[n]for(i=1; i<=n; ++i){   j = i;   j++;}

    这段代码中,第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2-6行,虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)


    复杂度速查表

    来源:https://liam.page/2016/06/20/big-O-cheat-sheet/ 源地址:https://www.bigocheatsheet.com/

    图例

    2544fed2bfb6e8dd9f8fc1704b2966fd.png

    大-O 复杂度曲线

    1b0ca67ad51c9cb983f4466b1e462e5b.png

    抽象数据结构的操作复杂度

    1a13196cf655fa39999b964d352b5bf1.png

    数组排序

    23efce16bb89c7a56fa3b6dfe64b2812.png

    图操作

    98eedf83b4cf20fb7079cdc74552c218.png

    堆操作

    bc5325f511f7bdbbae66a45040b40953.png

    参考

    《大话数据结构》 https://zhuanlan.zhihu.com/p/50479555

    展开全文
  • 感觉有时候评价一个算法的时间复杂度挺难的,特别是递归的时候,大家一般怎么看啊?
  • 高级工程师title我,最近琢磨着好好刷刷算法题更高级一些,然鹅,当我准备回忆大学和面试时候学数据结构之时,我发现自己对这个算法复杂度的记忆只有OOOOOooo算法(Algorithm)是指用来操作数据、解决程序问题的一...

    高级工程师title的我,最近琢磨着好好刷刷算法题更高级一些,然鹅,当我准备回忆大学和面试时候学的数据结构之时,我发现自己对这个算法复杂度的记忆只有OOOOOooo

    算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别。

    那么我们应该如何去衡量不同算法之间的优劣呢?

    主要还是从算法所占用的「时间」和「空间」两个维度去考量。

    • 时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。
    • 空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。

    因此,评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而,有的时候时间和空间却又是「鱼和熊掌」,不可兼得的,那么我们就需要从中去取一个平衡点。

    时间复杂度

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

    时间频度T(n)中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律,为此我们引入时间复杂度的概念。算法的时间复杂度也就是算法的时间度量,记作:T(n) = O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称「时间复杂度」。

    这种表示方法我们称为「 大O符号表示法 」,又称为渐进符号,是用于描述函数渐进行为的数学符号

    常见的时间复杂度量级有:

    • 常数阶
    • 线性阶
    • 平方阶
    • 立方阶
    • 对数阶
    • 线性对数阶
    • 指数阶

    常数阶

    ,表示该算法的执行时间(或执行时占用空间)总是为一个常量,不论输入的数据集是大是小,只要是没有循环等复杂结构,那这个代码的时间复杂度就都是O(1),如:

    int i = 1;int j = 2;int k = i + j;

    上述代码在执行的时候,它消耗的时候并不随着某个变量的增长而增长,那么无论这类代码有多长,即使有几万几十万行,都可以用来表示它的时间复杂度。

    线性阶

    ,表示一个算法的性能会随着输入数据的大小变化而线性变化,如

    for (int i = 0; i < n; i++) { j = i;   j++;}

    这段代码,for循环里面的代码会执行n遍,因此它消耗的时间是随着n的变化而变化的,因此这类代码都可以用来表示它的时间复杂度。

    平方阶

    ² 表示一个算法的性能将会随着输入数据的增长而呈现出二次增长。最常见的就是对输入数据进行嵌套循环。如果嵌套层级不断深入的话,算法的性能将会变为立方阶,,以此类推

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

    指数阶

    ,表示一个算法的性能会随着输入数据的每次增加而增大两倍,典型的方法就是裴波那契数列的递归计算实现

    int Fibonacci(int number){    if (number <= 1) return number;    return Fibonacci(number - 2) + Fibonacci(number - 1);}

    对数阶

    int i = 1;while(i

    上面的代码,在while循环里面,每次都将 i 乘以 2,乘完之后,i 距离 n 就越来越近了,直到i不小于n退出。我们试着求解一下,假设循环次数为x,也就是说 2 的 x 次方等于 n,则由2^x=n得出x=log₂n。因此这个代码的时间复杂度为

    线性对数阶

    线性对数阶,就是将时间复杂度为对数阶的代码循环n遍的话,那么它的时间复杂度就是 n * O(logN),也就是了,如下,

    for(m=1; m

    除此之外,其实还有平均情况复杂度、最好时间复杂度、最坏时间复杂度。。。一般没有特殊说明的情况下,都是值最坏时间复杂度。


    空间复杂度

    空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势,一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)),其中n为问题的规模,S(n)表示空间复杂度。

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

    一般情况下,一个程序在机器上执行时,除了需要存储程序本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身,和算法无关,这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数,则称此算法为原地工作,空间复杂度为O(1)。当一个算法的空间复杂度与n成线性比例关系时,可表示为,类比时间复杂度。

    空间复杂度比较常用的有:O(1)、O(n)、O(n²)

    空间复杂度

    如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1) 举例:

    int i = 1;int j = 2;++i;j++;int m = i + j;

    代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)

    空间复杂度

    int[] m = new int[n]for(i=1; i<=n; ++i){   j = i;   j++;}

    这段代码中,第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2-6行,虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)


    复杂度速查表

    来源:https://liam.page/2016/06/20/big-O-cheat-sheet/ 源地址:https://www.bigocheatsheet.com/

    图例

    69af943f019e4fcdc82f3492cf5b72e6.png

    大-O 复杂度曲线

    6768e82565d35c1de2cd9f066f423421.png

    抽象数据结构的操作复杂度

    1f0c36273b251cfef750f40a9058a50d.png

    数组排序

    e334011bf888990b42ccd6a6f57d4c08.png

    图操作

    75dc7792bd0f16b56b67fac4b63b9770.png

    堆操作

    b2368387cebbaa27ba419f2b3d252f92.png

    参考

    《大话数据结构》 https://zhuanlan.zhihu.com/p/50479555

    展开全文
  • python学习:算法和时间复杂度算法什么是算法?算法(Algorithm)是指解题方案的准确...同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个...

    python学习:算法和时间复杂度

    算法

    什么是算法?

    算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。

    算法也可以说是我们为了解决问题而编写的程序,它能够对一定规范的输入,在有限时间内获得所要求的输出。

    同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

    一个算法的评价主要从时间复杂度、空间复杂度、正确性、可读性、健壮性(容错性)这几个方面来考虑。

    算法的主要方法

    在解决问题时,采用的方法不同,可能会有多种不同的算法。常用解决问题的方法有:

    递推法:将复杂的庞大的计算过程转化为简单连续或重复的过程

    递归法:递归函数,在函数中调用本身

    分治法:将复杂问题逐步分解为较小问题,直到最后的小问题可简单解出

    迭代法:也叫辗转法,是一种不断用变量的旧值递推新值的过程

    回溯法:一种选优搜索法,按选优条件向前搜索,以达到目标

    贪心算法:以当前情况为基础根据某个条件作最优选择,而不考虑各种可能的选择,以迭代的方法做出相继的贪心选择

    动态规划法:将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。

    分支定界法:对有约束条件的最优化问题的所有可行解空间进行搜索。

    如何评价算法的优劣呢?比较简单、直观的评价方式就是 算法的运行时间或占用的空间

    时间复杂度

    算法运行时间

    影响因素:

    软件因素:机器编译代码的速度

    硬件因素:计算机硬件好坏

    算法因素:算法程序代码

    问题规模:需解决问题的规模大小

    推导:

    问题规模n条件下

    算法运行总时间-->

    每行代码运行时间之和-->

    单行代码执行次数f(n)-->

    大O复杂度表示法O(f(n))-->

    复杂度公式T(n)=O(f(n))

    求解步骤

    1.找出算法中的基本语句:执行次数最多的那条语句

    2.计算基本语句执行次数

    3.推算执行次数数量级:保证最高次项正确

    4.用大O表示

    计算法则

    (1).对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间

    (2).对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则"

    (3).对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间

    (4).对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"

    (5).对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度

    求和法则:设T1(n)=O(f(n)),T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))

    乘法法则:设T1(n)=O(f(n)),T2(n)=O(g(n)),则 T1T2=O(f(n)g(n))

    常见复杂度

    常数阶O(1)

    线性阶O(n)

    平方阶O(n²)

    对数阶O(logn)

    线性对数阶O(nlogn)

    a = 1

    b = a

    c = b

    执行时间与问题规模n无关,时间复杂度为常数阶,记T(n)=O(1)

    a = 0

    b = 100

    for i in range(n):

    a += i

    b -= i

    执行时间与问题规模n相关,执行次数f(n)=2n+2,时间复杂度为线性阶,记T(n)=O(n)

    x = 0

    y = 1

    for i in range(n):

    x += i

    for j in range(n):

    y *= j

    执行时间与问题规模n相关,执行次数f(n)=n^2+2,时间复杂度为平方阶,记T(n)=O(n^2)

    i = 1

    while i <= n:

    i *= 2

    执行时间与问题规模n相关,执行次数2^(f(n)-1)=n,时间复杂度为对数阶,记T(n)=O(logn)

    for j in range(n):

    i = 1

    while i <= n:

    i *= 2

    执行时间与问题规模n相关,时间复杂度为线性对数阶,记T(n)=O(nlogn)

    对时间复杂度的分析并不复杂,需要多多练习

    拓展:其他时间复杂度

    递归算法的时间复杂度(recursive algorithm time complexity):

    总体时间复杂度O(每个递归函数时间复杂度T*depth递归深度)

    最好情况时间复杂度(best case time complexity):

    算法在最好情况下执行代码的时间复杂度,运行时间最短的情况

    最坏情况时间复杂度(worst case time complexity):

    算法在最坏情况下执行代码的时间复杂度,运行时间最长的情况

    平均时间复杂度(average case time complexity):

    代码在所有可能情况下执行次数的加权平均值

    均摊时间复杂度(amortized time complexity):

    在代码执行的所有复杂度情况中绝大部分是低复杂度,个别情况是高复杂度且发生具有时序关系时,可以将个别高复杂度均摊到低复杂度上。

    展开全文
  • 算法的时间复杂度到底怎么算? 引言 假设计算机运行行简单语句算作次运算。 def func1(num): print("Hello, World!\n") # 需要执行 1 次 return 0 # 需要执行 1 次 那么上面这方法需要执行 2 次运算 def ...

    算法的时间复杂度到底怎么算?

    引言

    假设计算机运行一行简单语句算作一次运算。

    def func1(num):
        print("Hello, World!\n")       # 需要执行 1 次
        return 0                       # 需要执行 1 次
    

    那么上面这个方法需要执行 2 次运算

    def func2(num):
        for i in range(num):            
            print("Hello, World!\n")    # 需要执行 n 次
        return 0                        # 需要执行 1 次
    

    这个方法需要 (n + 1) = n + 1 次运算。

    为了方便描述, 我们用f(n) 代表某个方法完成处理n个数据时,需要执行运算的次数

    所以上面的例子中,func1的f(n) = 2 func2的f(n) = n + 1
    

    是不是感觉跟以前课本看见的不太一样, 以前课本都是什么O(n), O(n^2), O(1)等等, 别急,继续看

    什么是算法

    想计算算法的时间复杂度,首先要理解,什么是算法。

    算法,是一种抽象出来的逻辑范式,是解决特定问题的方法, 是一个def(python 语言)

    针对同一问题A,存在不同的解决方法(算法),
    智商高的人写出来的优秀算法,在小数据集上,优秀算法解决A只需要嗖嗖嗖,3秒。 
    普通智商的人抽象出来的算法,要吭哧吭哧, 4秒完成。 差距还不是很大。
    
    这时,让我们将数据量增大1W倍,优秀算法可能需要3W秒,普通算法就需要4W秒甚至更多。 这样的差距可就不可以接受了。
    

    那为什么计算时间会长,因为两个算法为了完成等量计算任务,执行运算的次数却不同。 普通算法可能在数值的比较和交换上明显多于优秀算法。 一旦数据量增大,消耗的时间也会显著增大

    在标准配置的CPU下,相差一万秒,计算次数相差可以达到万亿的水平。

    从此,不同算法有了优劣之分。 那如何评价算法的优劣呢,时间复杂度就来了。

    那什么是算法的时间复杂度?

    简单的来说,时间复杂度是用来概括描述算法运行时间和数据量n之间的关系。 记作T(n)

    T(n)可以当做是算法执行时间的衡量,也可以是描述算法优劣和数据量n之间的一个函数。

    更直白的说,时间复杂度T(n)=算完刚才那道题A需要用的时间的大概估计 = 算完刚才那道题A需要用执行的运算次数f(n)

    所以最开始的两个例子,func1的f(n) = 2 = T(n) func2的f(n) = n + 1 = T(n) 是不是更顺眼了一点。
    f(n) 不止代表运算次数,还可以代表算法的运行时间了(在相同配置的CPU下)
    

    那大O记号又是什么, 为什么书里都是这些圆圈O

    首先,大O记号是一种运算符,跟±*%一样,要有一个这样的预设。

    大O记号完成的是约等于的功能。 想象math.floor() 或者 math.ceil(),都是约等于的功能。
    具体的, O(2 * n^2 + 3) = O(n^2) O(2^n + n^2) = O(2^n) 大概就是这样估计的

    量级高(阶数大)的可以直接覆盖量级低(阶数小)的,同时将倍数置成1

    量级参考:
    O(1) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) <O(n!)
    

    知道了大O记号,现在给出T和O之间的关系是 T(n) = O(f(n))

    为了方便描述和简便计算,大家习惯用大O记号近似表示运行时间和数据规模之间关系。

    上面的两个例子,func1的T(n) = f(n) = 2 = O(2) = O(1)
    func2的T(n) = f(n) = n + 1 = O(n + 1) = O(n)
    

    就像,面试官问你这个算法时间复杂度是多少,你会说O(n) 而不是 n + 1, 不然面试官可能会把你踢出去。

    O(1) 表示算法有限次执行,跟数据量无关
    O(n) 表示算法运次时间跟数据量呈一次线性关系。

    那么f(n) 和T(n) 到底有是什么关系

    (这段不想看可以忽略,就记住T(n) = f(n) 就成)

    弄清这两个的关系,又要说到刚才的大O记号了

    但在此之前,首先要明确,f(n) 是描述算法运算次数与数据量之间的一个函数(比如 f(n) = n + 1)

    是因为方便描述,我们才引入了大O记号,因为我们习惯说,“这个算法的时间复杂度是跟数据量呈线性关系的”,而不是说,“这个算法的时间复杂度和数据量呈现2倍加2的关系”。

    接着我们定义:存在常数 c 和函数 f(n),使得当 n >= c 时 T(n) <= f(n),我们称T(n)以f(n)为界或者称T(n)受限于f(n)。 然后给出T(n) = O(f(n))

    以f(n)为界,也就是无论自变量n如何取,T(n)的值永远都不会超过f(n), 我们用一个对大数的估计,来表示T(n)的增长幅度。 所以才有这个式子T(n) = O(f(n))

    那如何计算f(n),算法的执行次数呢?

    1. 对于一个循环,默认循环体的执行次数为 1,循环次数为 n,则这个
      循环的时间复杂度为 O(1xn)。
    def func3(num):
        for i in range(num):            # 执行次数为 num
            print("Hello, World!\n")    # 循环体执行为 1                     
    

    此时时间复杂度为 O(num × 1),即 O(n)。

    1. 对于多个循环,默认循环体的执行次数为 1,从内向外,各个循环的循环次数分别是a, b, c…,则这个循环的时间复杂度为 O(1×a×b×c…)。
    def func4(num):
        for i in range(num):                # 循环次数为 num
            for j in range(num):            # 循环次数为 num
                print("Hello, World!\n")    # 循环体执行为 1                    
    

    此时时间复杂度为 O(num × num × 1),即 O(n^2)。

    1. 对于顺序执行的语句或者算法,总的时间复杂度等于其中最大的时间复杂度。
    def func5(num):
        for i in range(num):                # 循环次数为 num
            for j in range(num):            # 循环次数为 num
                print("Hello, World!\n")    # 循环体执行为 1  第一部分时间复杂度为 O(n^2)
    
        for k in range(num):                # 循环次数为 num
            print("Hello, World!\n")        # 循环体执行为 1  第二部分时间复杂度为 O(n)    
    

    此时时间复杂度为 max(O(n^2), O(n)),即 O(n^2)。

    1. 对于条件判断语句,总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度。
    def func6(num):
        if (num >= 0):
            for i in range(num):                # 循环次数为 num
                for j in range(num):            # 循环次数为 num
                    print("Hello, World!\n")    # 循环体执行为 1  第一部分时间复杂度为 O(n^2)
        else:
            for k in range(num):                # 循环次数为 num
                print("Hello, World!\n")        # 循环体执行为 1  第二部分时间复杂度为 O(n)    
    

    此时时间复杂度为 max(O(n^2), O(n)),即 O(n^2)。

    时间复杂度分析的基本策略是:从内向外分析,从最深层开始分析。如果遇到函数调用,要深入函数进行分析。

    最后,我们来练习一下

    • 基础题
      求该方法的时间复杂度
    def  exe1(n):
        for i in range(n):                  # 循环次数为 n
            for j in range(i, n):           # 循环次数为 n - i
                print("Hello, World!\n")    # 循环体时间复杂度为 O(1)                     
    

    参考答案:
    当 i = 0 时,内循环执行 n 次运算,当 i = 1 时,内循环执行 n - 1 次运算……
    当 i = n - 1 时,内循环执行 1 次运算。
    所以,执行次数 f(n) = n + (n - 1) + (n - 2)……+ 1 = n(n + 1) / 2 = n^2 / 2 + n / 2
    f(n)的最高次是n^2

    所以 T(n) = O(f(n)) = O(n^2 / 2 + n / 2) = O(n^2) 该算法的时间复杂度为 O(n^2)

    • 进阶题
      求该方法的时间复杂度
    def  exe2(n):
        for i in range(2, n):             
            i *= 2                          # 循环体时间复杂度为 O(1)
            print("Hello, World!\n")        # 循环体时间复杂度为 O(1)                     
    

    参考答案:
    假设循环次数为 t,则循环条件满足 2^t < n。
    可以得出,执行次数t = log(2)(n),即 f(n) = log(2)(n),
    可见时间复杂度为 T(n) = O(log(2)(n)),即 O(log n)。

    • 再次进阶
      求该方法的时间复杂度
    def exe3(n):
        if (n <= 1):
            return 1
        else:
            return exe3(n - 1) + exe3(n - 2);    
    

    参考答案:
    显然运行次数,f(0) = f(1) = 1,同时 f(n) = f(n - 1) + f(n - 2) + 1,这里的 1 是其中的加法算一次执行。
    显然 f(n) = f(n - 1) + f(n - 2) 是一个斐波那契数列,通过归纳证明法可以证明,
    当 n >= 1 时 f(n) < (5/3)^n,同时当 n > 4 时 f(n) >= (3/2)^n。

    所以该算法的时间复杂度可以表示为 O((5/3)^n),简化后为 O(2^n)。

    参考

    1. https://www.jianshu.com/p/f4cca5ce055a
    2. https://www.zhihu.com/question/20196775
    展开全文
  • 学习算法的同学,如果不知道计算一个算法的时间复杂度该如何计算,其实是一件很丢脸的事情。最近选修了高级算法这门课,由于时间紧张,原本就想混过去了,但是不料考试的时候有40%的题目是计算时间复杂度的,干脆...
  • 一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面,所需的资源越多,我们就说该算法的复杂性越高;反之,所需的资源越低,则该算法的复杂性越低。 计算机的资源,最重要的是时间和空间(即...
  • 算法的时间复杂度一个算法中他的计算次数T(n)就是分析时间复杂度的标杆 当随着n增大,T(n)增长最慢的算法称为最优算法 具体怎么算呢:以下是大O阶算法 1.首先计算出T(n),用常数1取代所有加法的常数 2.在修改...
  • 时间复杂度怎么算

    2019-11-28 00:05:29
    一、什么是时间复杂度? 一个语句的频度是指该语句在算法中重复执行的次数,算法中所有语句的频度之和是关于问题规模n的...二、常见的时间复杂度排序 O(1) < O()<O(n)<O(n)<O()<O()<O()<O(n...
  • 学习算法的同学,如果不知道计算一个算法的时间复杂度该如何计算,其实是一件很丢脸的事情。最近选修了高级算法这门课,由于时间紧张,原本就想混过去了,但是不料考试的时候有40%的题目是计算时间复杂度的,干脆...
  • 首先要明确一个概念,变量的内存分配发生在定义的时候 忽略常数,用O(1)表示 递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间 对于单线程来说,递归有运行时堆栈,求的是递归最深的那一次压栈所耗费的...
  • 作者 | Lee在研究排序算法的时候,我们经常会听到时间复杂度的概念。很多时候只是习惯性的记下来,但是怎么来的,却很少能够研究明白。于是在笔试题中,经常要求时间复杂度为O(n),就很懵。解决同样的问题,不同的...
  • CarlSun究竟什么是时间复杂度时间复杂度就是用来方便开发者估算出程序的运行时间我们该如何估计程序运行时间呢,我们通常会估计算法的操作单元数量,来代表程序消耗的时间, 这里我们默认CPU的每单元运行消耗...
  • 排序算法法界是一个怎么存在?就好像在学术界中数学地位,说直接用好像用不上,可是不会做起事情来总会捉襟见肘,左支右绌。找工作时候,有面试官甚至会让我们手写排序算法。既然排序算法如此重要,就...
  • 递归到底是个啥?...递归函数运行时,实际上会进行一个压栈(思考栈特点,先进后出,后进先出)过程。 写个简单递归排序算法: public static void main(String[] args) { int[] arr={1,3,4...
  • 【转载】时间复杂度到底怎么算 时间复杂度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法...
  • 算法(Algorithm)是指用来操作数据、解决程序问题的组方法。...时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。空间维度:是指执行当前算法需要占用多少内存空间,我们通常...
  • 经常听人谈起各种排序算法的时间复杂度,这个是O(n2)的,那个是O(n)的,这些人讲起来可谓滔滔不绝,但是你停下来问问他为什么这个是这个复杂度,他是怎么算出来的?往往没几个人能说出来。这个是一个浮躁的社会,...
  • 学习算法的同学,如果不知道计算一个算法的时间复杂度该如何计算,其实是一件很丢脸的事情。最近选修了高级算法这门课,由于时间紧张,原本就想混过去了,但是不料考试的时候有40%的题目是计算时间复杂度的...
  • 高级工程师title我,最近琢磨着好好刷刷算法题更高级一些,然鹅,当我准备回忆大学和面试时候学数据结构之时,我发现自己对这个算法复杂度的记忆只有OOOOOooo 文章收录在 GitHub JavaKeeper ,N线互联网开发必备...
  • 二叉树的算法时间复杂度

    千次阅读 2019-09-23 19:15:23
    二叉搜索树,平衡二叉树,红黑树的算法效率 操作二叉查找树平衡二叉树红黑树 查找 O(n) ...Olog(n)怎么算出来一个树中查找一个数字, 第一次在根节点判断,第二次在第二层节点...
  • 经常听人谈起各种排序算法的时间复杂度,这个是O(n2)的,那个是O(n)的,这些人讲起来可谓滔滔不绝,但是你停下来问问他为什么这个是这个复杂度,他是怎么算出来的?往往没几个人能说出来。这个是一个浮躁的社会,...
  • 究竟什么是时间复杂度时间复杂度就是用来方便开发者估算出程序的运行时间我们该如何估计程序运行时间呢,我们通常会估计算法的操作单元数量,来代表程序消耗的时间, 这里我们默认CPU的每单元运行消耗的时间都是...
  • 我们知道,时间复杂度和“大O表示法”是我们经常会碰到概念,他们是用来衡量算法优劣度量,那具体怎么算的呢?来看一下 2、引例 在抛出概念之前,咱先来例子: 如果 a+b+c=1000,且 a^2+b^2=c^2(a,b,c 为...
  • Dijkstra算法时间复杂度

    万次阅读 2013-08-21 13:29:45
    question: 我只知道是O(n2),不知道怎么算来的,请详细讲一下。 网上搜全都是这句话: Dijkstra 算法最简单的实现方法...这样的话算法的运行时间是 O(n2)。 没说怎么得到这n2的. 附算法: 1 function
  • 时间复杂度

    2015-10-30 21:41:38
    学习算法的同学,如果不知道计算一个算法的时间复杂度该如何计算,其实是一件很丢脸的事情。最近选修了高级算法这门课,由于时间紧张,原本就想混过去了,但是不料考试的时候有40%的题目是计算时间复杂度的,干脆...

空空如也

空空如也

1 2 3 4 5
收藏数 82
精华内容 32
关键字:

一个算法的时间复杂度怎么算