精华内容
下载资源
问答
  • 一个算法的时间复杂度怎么算
    千次阅读
    2020-06-14 02:54:31

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

    引言

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

    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
    更多相关内容
  • 算法复杂度分为时间复杂度和空间复杂度。 其作用: 时间复杂度是指执行算法所需要的计算工作量; 而空间复杂度是指执行这...算法时间复杂度一个函数,它定量描述了该算法的运行时间,时间复杂度常用“O”表述,使
  • 算法时间复杂度

    2017-11-02 22:28:24
    算法时间复杂度
  • 根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导
  • 以堆排序算法为例,改变输入规模n,测试算法时间复杂度
  • 算法时间复杂度实验报告.doc
  • 对于每一个设计出来的算法都需要从这两个方面来分析 O(N), O(N^2) : o notation #%% int a = 0, b = 0; for (i = 0; i < N; i++) { # O(N)+O(N)=2*O(N)=O(N) a = a + rand();# N*1个操作 = O(N) b = b + rand...
  • 算法设计与复杂度分析 算法复杂性分析 算法复杂性是算法运行所需要的计算机资源的量 需要时间资源的量称为时间复杂性,需要的空间资源的 量称为空间复杂性这量应该只依赖于算法要解的 题的规模算法的输入和算法本身...
  • 算法时间复杂度计算

    千次阅读 2022-05-12 23:18:25
    计算算法时间复杂度分析一、简单循环及其变种二、层层影响循环总结 分析 算法中所有语句的频度之和记为T(n),它是该算法问题规模n的函数。 对于一个算法来说,循环体和递归是时间复杂度的重灾区,在这里先分析循环体...

    2022.5.12


    分析

    算法中所有语句的频度之和记为T(n),它是该算法问题规模n的函数。
    对于一个算法来说,循环体和递归是时间复杂度的重灾区,在这里先分析循环体的时间复杂度。

    预备知识:
    1.常见渐进时间复杂度
    

    O(1)<o(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)

    2.计算时间复杂度时,系数可省略,O记法只看加项的最高阶
    

    一、简单循环及其变种

    [例1]
    
    void fun(int n)
    {
    int i=1;         //语句频度1,后期可以忽略
    while(i<=n)      //i<=n是循环条件
    i=i*2;           //i=i*2控制循环次数
    }
    

    这里我们计算时间复杂度需要计算的就是循环体的语句频度。
    设循环次数:t
    根据循环体可得:2t<=n,此时循环可以继续下去
    接下来只需求解出:t<=log2n,即可得到T(n)=O(log2n)
    此时的t对应的就是语句的频度。

    [例2]
    
    void fun(int n)
    {
    int i=1;             //语句频度1,后期可以忽略
    while(i*i*i<=n)      //i*i*i<=n是循环条件
    i++;                 //i++和i*i*i控制循环次数
    }
    

    这里我们依旧计算循环体的语句频度。
    设循环次数:t
    根据循环体可得:t=i,t3<=n,此时循环可以继续下去
    接下来只需求解出:t<=3√n ,即可得到T(n)=O(3√n)
    此时的t对应的就是语句的频度。

    [例3]
    
    void fun(int n)
    {
    int x=2;             //语句频度1,后期可以忽略
    while(x<n/2)         //x<n/2是循环条件
    x=2*x;               //x=2*x和n/2控制循环次数
    }
    

    这里我们依旧计算循环体的语句频度。
    设循环次数:t
    根据循环体可得:2t+1<n/2,此时循环可以继续下去
    接下来只需求解出:t<log2n-2 ,即可得到T(n)=O(log2n)
    此时的t对应的就是语句的频度。

    [例4]
    
    void fun(int n)
    {
    int x=0;                      //语句频度1,后期可以忽略
    while(n>=(x+1)*(x+1))         //n>=(x+1)*(x+1)是循环条件
    x=x+1;                        //x=x+1和(x+1)*(x+1)控制循环次数
    }
    

    这里我们依旧计算循环体的语句频度。
    设循环次数:t
    根据循环体可得:(t+1)2<=n,此时循环可以继续下去
    接下来只需求解出:t<=√n-1 ,即可得到T(n)=O(√n)
    此时的t对应的就是语句的频度。

    [例5]
    
    void fun(int n)
    {
    int count=0;                   //语句频度1,后期可以忽略
    for(k=1;k<=n;k*=2)             //k<=n是循环条件
    for(j=1;j<=n;j++)              //j<=n是循环条件
    count++;                       //k*=2和j++控制循环次数
    }
    

    这里我们依旧计算循环体的语句频度。
    设循环次数:t1和t2
    根据循环体可得:2t1<=n且t2<=n,此时循环可以继续下去
    接下来只需求解出:t1<=log2n和t2<=n ,总循环次数t=t1xt2,即可得到T(n)=O(nlog2n)
    此时的t对应的就是语句的频度。

    二、层层影响循环

    [例6]
    
    void fun(int n)
    {
    for(i=n-1;i>1;i--)             //i>1是循环条件
    for(j=1;j<i;j++)               //j<i是循环条件
    if(A[j]>A[j+1];                //i--和j++控制循环次数
    A[j]与A[j+1]互换;
    }
    

    这里的循环体是多层嵌套且相互关联的,所以在计算时要采用其它方式。
    由循环体可以列出:
    T ( n ) = ∑ i = 2 n − 1 ∑ j = 1 i − 1 1 = ( n − 1 ) ( n − 2 ) 2 T(n)=∑_{i=2}^{n-1} ∑_{j=1}^{i-1}1 =\displaystyle { \frac{(n-1)(n-2)}{2} } T(n)=i=2n1j=1i11=2(n1)(n2)
    直接得到T(n)=O(n2)

    [例7]
    
    void fun(int n)
    {
    int m=0,i,j;                 //语句频度1,后期可以忽略
    for(i=1;i<=n;i++)            //i<=n是循环条件
    for(j=1;j<=2*i;j++)          //j<=2*i是循环条件
    m++;                         //2*i和i++和j++控制循环次数
    }
    

    由循环体可以列出:
    T ( n ) = ∑ i = 1 n ∑ j = 1 2 i 1 = ( 2 n + 2 ) n 2 T(n)=∑_{i=1}^{n } ∑_{j=1}^{2i}1 =\displaystyle { \frac{(2n+2)n}{2} } T(n)=i=1nj=12i1=2(2n+2)n
    直接得到T(n)=O(n2)

    [例8]
    
    void fun(int n)
    {
    int m=0;
    for(i=1;k<=n;i++)          //k<=n是循环条件
    for(j=1;j<=i;j++)          //j<=i是循环条件
    for(k=1;k<=j;k++)          //k<=j是循环条件
    m++;                       //k++和i++和j++控制循环次数
    }
    

    由循环体可以列出:
    T ( n ) = ∑ i = 1 n ∑ j = 1 i ∑ k = 1 j 1 = [ ( n + 1 ) n 2 + 1 ] ∗ n / 2 T(n)=∑_{i=1}^{n } ∑_{j=1}^{i}∑_{k=1}^{j}1 =[\displaystyle { \frac{(n+1)n}{2} +1]*n/2} T(n)=i=1nj=1ik=1j1=[2(n+1)n+1]n/2
    直接得到T(n)=O(n3)


    总结

    所有题目来自王道书。
    可以对比例5和后面几个多层循环,当不同的层互不影响时,就能够将不同层分开计算。

    展开全文
  • 本篇文章是对php中的常用算法以及时间复杂度进行了详细的分析介绍,需要的朋友参考下
  • 选择排序、冒泡排序、归并排序、快速排序、插入排序的算法原理。不同排序算法时间效率的经验分析方法,验证理论分析与经验分析的一致性。
  • 时间复杂度算法运算所消耗的时间,因为不同大小的输入数据,算法处理所要消耗的时间是不同的,因此评估一个算运行时间是比较困难的,所以通常关注的是时间频度,即算法运行计算操作的次数,记为T(n),其中n称为...
  • 为了便于比较同一个问题的不同算法,通常做法是,从算法中选取一种对于所研究的问题来说是基本操作的原操作,以该基本操作重复执行的次数做为算法的时间量度。基本操作应是其重复执行次数和算法时间成正比的原操作,...

    1. 时间复杂度

    时间复杂度是指程序运行从开始到结束所需要的时间。时间复杂度的计算一般比较麻烦,故在数据结构的研究中很少提及时间复杂度。为了便于比较同一个问题的不同算法,通常做法是,从算法中选取一种对于所研究的问题来说是基本操作的原操作,以该基本操作重复执行的次数做为算法的时间量度。基本操作应是其重复执行次数和算法时间成正比的原操作,多数情况下它是最深层循环内的语句中的操作。算法的执行次数还要随输入集有关,此时要考虑所有可能输入数据的期望值,此时的算法时间复杂度叫平均时间复杂度。有事平均时间复杂度难以确定,此时分析最坏情况下算法的一个上界,此时称为最坏时间复杂度。

    2. 时间复杂度的表示方法

    设解决一个问题的规模为n,基本操作被重复执行次数是n的一个函数f(n),则时间复杂度可记作: T(n)=O(f(n)) 它表示随着问题规模n的增长,算法执行时的增长率和f(n)的增长率相同。其中T(n)叫算法的渐进时间复杂度,简称时间复杂度。算法的时间复杂度考虑的只是对于问题规模n的增长率,则在难以精确计算的情况下,只需考虑它关于n的增长率或阶即可。

    例如

    for(i=2;i<=n;++i)

    for(j=2;j<=i-1;++j)

    {

    ++x;

    a[i,j]=x;

    }

    其中++x语句频度为:1+2+3+…+n-2=(n-1)(n-2)/2=(n2-3n+2)/2故算法的时间复杂度可表示为:T(n)=O(n2)

    3. 时间复杂度的计算方法

    时间复杂的推导方法一般如下:

    第一步:用常数1取代运行时间中的所有加法常数。

    第二步:在修改后的运行次数函数中,只保留最高阶项。

    第三步:如果最高阶项存在且不是1,则去除与这个项相乘的常数。

    时间复杂度一般分为以下几种,分别是:

    (1)常数阶 首先顺序结构的时间复杂度。

    48304ba5e6f9fe08f3fa1abda7d326ab.png

    main()

    {

    int sum=0,n=100;

    sum=(1+n)*n/2;

    printf(“%d”,sum);

    }

    48304ba5e6f9fe08f3fa1abda7d326ab.png

    算法的时间复杂度为O(1)。 这个算法的运行次数函数是f(n)=3。根据我们推导的方法,第一步就是把常数项3改为1。在保留最高阶项时发现,它根本没有最高阶项,所以这个算法的时间复杂度为O(1)。

    (2)线性阶 要确定某个算法的阶次,需要确定某个特定语句或某个语句集运行的次数。因此,要分析算法的复杂度,关键就是要分析循环结构的运行情况。

    int i; for(i=0;i

    {

    /*时间复杂度为O(1)的程序步骤序列*/

    }

    (3)对数阶

    int count=1;

    while(count

    { count=count*2; /*时间复杂度为O(1)的程序步骤序列*/}

    由于每次count乘以2之后,就距离n更近了一点。也就是说,有多少个2相乘后大于n,则会退出循环。由2x=n得到x=log2n。所以这个循环的时间复杂度为O(log2n)。

    (4)平方阶

    48304ba5e6f9fe08f3fa1abda7d326ab.png

    inti,j;

    for(i=0;i

    {

    for(j=0;j

    { /*时间复杂度为O(1)的程序步骤序列*/

    }

    }

    循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。间复杂度为O(n2)。

    4. 总结

    本文主要讨论算法的时间复杂度,算法时间复杂度在数据结构中是比较难的问题,通过本文给出的计算时间复杂度的方法,能够比较容易掌握时间复杂的计算。

    展开全文
  • 时间复杂度与空间复杂度1.算法的复杂度:2....​ 空间复杂度: 是对一个算法在运行过程中临时占用存储空间大小的量度; 算法的复杂性体运行该算法时的计算机所需资源的多少上,计算机资源最重要的是时间和空间(即

    1.算法的复杂度:

    算法的时间复杂度和空间复杂度合称为算法的复杂度。

    时间复杂度: 时间复杂度是指执行算法所需要的计算工作量;

    空间复杂度: 是对一个算法在运行过程中临时占用存储空间大小的量度;

    算法的复杂性体运行该算法时的计算机所需资源的多少上,计算机资源最重要的是时间和空间(即寄存器)资源,因此复杂度分为时间和空间复杂度。

    2.时间复杂度:

    一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度,记为T(n)。

    一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f (n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
    在这里插入图片描述

    1.大O表示法:

    用O( )来体现算法时间复杂度的记法,我们称之为大O表示法。

    算法复杂度可以从最理想情况、平均情况和最坏情况三个角度来评估,由于平均情况大多和最坏情况持平,而且评估最坏情况也可以避免后顾之忧,因此一般情况下,我们设计算法时都要直接估算最坏情况的复杂度。大O表示法所表示的是一个算法在最糟糕情况下的运行时间。

    2.大O推导方法:

    1.用常数1来取代运行时间中所有加法常数。

    2.修改后的运行次数函数中,只保留最高阶项

    3.最高项除去其相乘的常数,得到的结果就是大O阶。

    举例:

    单个循环体情况:

    void Demo(int n){
    		for(int j = 0; j < n; j++) {        // 循环次数为 n
                printf("Hello, World!\n");      // 循环体时间复杂度为 O(1)
            }
    }
    //时间复杂度为 O(n × 1),即 O(n)。
    

    多重循环体情况:

    void Demo(int n) {
    for(int i = 0; i < n; i++) {            // 循环次数为 n
            for(int j = 0; j < n; j++) {        // 循环次数为 n
                printf("Hello, World!\n");      // 循环体时间复杂度为 O(1)
            }
        }
    }   
    //时间复杂度为 O(n × n × 1),即 O(n^2)。
    

    多个事件复杂度情况:

    void Demo(int n) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                printf("Hello, World!\n");// 第一部分时间复杂度为 O(n^2)
            }
        }
        for(int j = 0; j < n; j++) {
            printf("Hello, World!\n");// 第二部分时间复杂度为 O(n)
        }
    }
    //时间复杂度为 max(O(n^2),O(n)),即 O(n^2)。
    

    3.一些常见的大O运行时间:

    • O(log n),对数时间,二分查找。
    • O(n),线性时间,简单查找。
    • O(n logn),快速排序——速度较快的排序算法。
    • O(n²),选择排序——速度较慢的排序算法。
    • O(n!),旅行商问题的解决方案——非常慢的算法。

    3.空间复杂度:

    一个程序的空间复杂度是指运行完一个程序所需内存的大小,利用程序的空间复杂度,可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。

    (1)固定部分:这部分空间的大小与输入/输出的数据的个数多少、数值无关,主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间,这部分属于静态空间。

    (2)可变空间:这部分空间的主要包括动态分配的空间,以及递归栈所需的空间等,这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)),其中n为问题的规模,S(n)表示空间复杂度。

    通常来说,只要算法不涉及到动态分配的空间以及递归、栈所需的空间,空间复杂度通常为0(1)。

    4.个别特殊举例:

    1.斐波那契数列的时间和空间复杂度

    //递归情况下的斐波那契数列
        public static int Fib(int num){
            if (num==1||num==2){
                return num;
            }
            return Fib(num-2)+Fib(num-1);
        }
    

    递归的时间复杂度是: 递归次数*每次递归中执行基本操作的次数,所以,时间复杂度是: O(2^N)。

    递归的空间复杂度是: 递归的深度*每次递归所需的辅助空间的个数,所以,空间复杂度是:O(N)。

    2.二分法的时间复杂度和空间复杂度

    二分查找在最坏的情况下依次是n/2,n/4,n/8一直到1为止。
    假设是x次,然后我们可以观察到分母是每次都乘以1/2,分子不变,所以可以列出下面等式:

    n(1/2)^x = 1

    通过计算得出x=log2N,即时间复杂度为O(log2N);

    非递归:

    public static int binarySearch(int[] arr,int toFind) {
            int left = 0;
            int right = arr.length-1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (arr[mid] < toFind) {
                    left = mid + 1;
                }
                else if (arr[mid] > toFind) {
                    right = mid - 1;
                }
                else {
                    return mid;
                }
            }
            return -1;
        }
    

    时间复杂度:循环的基本次数是log2N,所以,时间复杂度是O(log2N);

    空间复杂度:由于辅助空间是常数级别的,所以,空间复杂度是O(1)。

    递归:

    public static int binarySearch(int srcArray[], int start, int end, int key) {
            int mid = (end - start) / 2 + start;
            if (srcArray[mid] == key) {
                return mid;
            }
            if (start >= end) {
                return -1;
            } else if (key > srcArray[mid]) {
                return binarySearch(srcArray, mid + 1, end, key);
            } else if (key < srcArray[mid]) {
                return binarySearch(srcArray, start, mid - 1, key);
            }
            return -1;
        }
    

    递归的次数和深度都是log2N,每次所需要的辅助空间都是常数级别的:
    时间复杂度 : O(log2N)
    空间复杂度:O(log2N)

    展开全文
  • 算法时间复杂度的计算

    千次阅读 2019-08-25 16:48:57
    算法时间复杂度定义 在进行算法分析时候,语句总的执行次数T(n)是关于问题规模n的函数,进而分型T(n)随着n的变化情况并确定T(n)的数量级.算法的时间复杂度,也就是算法的时间度量记作:T(n)=O(f(n)).它表示随着...
  • Dijkstra算法时间复杂度分析

    万次阅读 多人点赞 2021-02-24 20:35:04
    之前一直默认Dijkstra算法时间复杂度为 o(n2)o(n^{2})o(n2),没有思考过具体的时间复杂度,今天把这弄清楚。 Dijkstra算法的思路与关键点 思路:广度优先 + 松弛 所有点分为两集合SSS和TTT,SSS最开始只包括...
  • 如何分析一个算法时间复杂度

    千次阅读 多人点赞 2020-04-21 11:07:35
    一直以来,分析一个算法时间复杂度对我而言都是很头疼的。直到今天又拿起数据结构… 算法时间复杂度就是一个算法执行次数的量级,而量级就是多项式的最高次幂。假如代码的执行次数是n(n+1)/2,那最高次幂是n^2,...
  • 两个阶非负整数方阵相乘,常规算法时间复杂度为O(ft),文献提出一个“运算次数”为口(xz)M"最佳”算法,文献(21对此算法做了进一步研究,提出三种改进策略。本文根据算法分析理论,得出改进后的算法时间复杂度仍不...
  • 快速排序时间复杂度: N数据 第1次分成2组=2^1 第2次分成4组=2^2 ...所以 t = log2N 也就是logN ,也就是空间复杂度为 logN 在每次排序里,又遍历了所有数据,所以每次的时间复杂度是 N 所以,.
  • 算法时间复杂度

    千次阅读 2022-03-05 19:40:47
    2.一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法时间复杂度记做:T(n)=O(f(n))。随着模块n的增大,算法执行的时间的增长率和f(n)的增长率成正比,所以f(n)越小,算法...
  • 时间复杂度(time complexity),是评估算法好坏的一个指标,关于它的本质,简单概括就是:时间复杂度一个算法的输入和它运行所需的时间之间的函数特征。 我们把这个输入称之为问题规模,而这个函数特征,并不是...
  • 算法复杂度分为时间复杂度和空间复杂度。 时间复杂度用于度量算法执行的时间长短;而空间复杂度则是用于度量算法所需存储空间的大小。 目录 时间复杂度 1.时间频度 2.计算方法 3.分类 空间复杂度 算法时间...
  • 应用马尔科夫链模型证明了遗传禁忌搜索算法是以概率1收敛到全局最优解的,并应用求解随机算法时间复杂度的方法,即求解算法的期望收敛时间,估算了该算法的时间复杂度,结果证明该算法的时间复杂度与所得解的多样性、...
  • NOIP普及组 提高组 CSP-J CSP-S初赛 算法时间复杂度部分题目.pdf
  • 算法时间复杂度-总结

    千次阅读 2021-10-17 19:52:35
    种简单粗暴衡量算法时间复杂度的方法(事后统计)通过预先估算来得到算法复杂度的方法(事前分析)时间复杂度概念[1]二、时间复杂度求解具体步骤常见法则总结 前言 假定有两算法,都能实现相同功能(算法均正确...
  • 算法时间复杂度分析()

    万次阅读 2019-07-03 22:50:59
    具体点来讲就是我们在实现某算法的时候,最终目的就是要求计算机(CPU)在最短的时间内,用最少的内存稳定的输出正确的结果。这章节主要来理解 “快”,至于“省” 和 “稳”,我会在后续章节进行讲解。 那如何...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 571,336
精华内容 228,534
热门标签
关键字:

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