精华内容
下载资源
问答
  • 0_时间复杂度的计算

    2019-11-18 12:14:22
    算法复杂度 算法复杂度分为时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量;...如何计算一个程序的时间复杂度 如下面一代码,如何计算的时间复杂度呢? int a= 10; int b= 10...

    算法复杂度

    算法复杂度分为时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。

    时间复杂度是学习算法的基石,因此在学习算法之前,必须要知道如何去计算一段代码的时间复杂度,下面就根阿导一起来看看吧。

    如何计算一个程序的时间复杂度

    如下面一段代码,如何计算它的时间复杂度呢?

    
        int a= 10;
        
        int b= 10;
        
        System.out.println(a+b);
        
    
    

    这个应该是很简单的,一眼就能看出来,其时间复杂度是 O(1),那接下来稍微来个复杂一点的

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

    有经验的程序员都知道上面的代码时间复杂度为 O(n),那么时间复杂度究竟是如何推导出来的呢?下面请允许阿导娓娓道来。

    假定每一句执行的时间都是 k,下面我将上述按照执行时间来划分,如下图所示

    时间划分执行代码语句

    红色代码代码部分执行时间为 3k,原谅色代码部分执行时间为 (n+1)k,蓝色代码部分执行时间为 2nk。

    那么上述代码执行时间可表示为 f(n) = (3n+4)k,明显这就是一个函数式,下面会涉及到一个量级的概念,就是将 n 趋近无穷大,然后得出最终渐进结果即为该段代码的时间复杂度,怎么理解呢,如下表所示:

    n f(n) = (3n+4)k
    1 7k
    100 304k
    10000 30004k
    100000000 300000004k
    10000000000000000 30000000000000004k

    你会发现,当 n 变成无穷大的时候,系数的影响微乎其微,我们只关注函数结果影响最大的项,因此上段代码我们会将其复杂度表示为 O(f(n))~O(n)。

    既然引出量级的概念,那么在计算复杂度的时候,存在不同的量级就会舍去低的量级,下面给出数学中量级比较关系,如下图所示

    数学中量级比较

    小结

    笔至此处,已渐尾声,下面我将计算复杂度的流程整理一遍。

    • 先假定每一句执行代码时间为 k

    • 然后分析代码语句,并得出执行时间的数学表达式

    • 接下来就是简化数学表达式,首先将 k 至为 1

    • 将所有常数替换成 1

    • 只保留高阶项(也就是量级最大的一项)

    • 去掉系数,得出最终结果即为时间复杂度

    不知各位看官是否已明了,如有疑问,欢迎留言,如有不当之处,请多多包涵和指教!

    展开全文
  • 如何计算算法的复杂度

    千次阅读 2019-07-16 17:39:03
    我们来看一个简单的程序 int n = 10 ; System.out.println("输出" + n); 这伪代码运行了多少次呢! 1次 ,时间时间复杂度为O(1):常数复杂度/常数阶。 for (int i = 0 ;i <n; i++){ Sy...

    目录

    时间复杂度

    空间复杂度

    总结


    时间复杂度

    什么叫做时间复杂度呢??

    我们来看一个简单的程序

     int n = 10 ;
    System.out.println("输出" + n);

     这段伪代码运行了多少次呢! 1次 ,时间时间复杂度为O(1):常数复杂度/常数阶。

            for (int i = 0 ;i <n; i++){
                System.out.println("第几次"+i);
            }

    这个for循环了多少次呢! n次,时间复杂度为O(n):线性时间复杂度。

    再看下一个

            for (int i = 0 ;i <n; i++){
                for (int j = 0 ;j < n; j ++) {
                    System.out.println("第几次" + i+""+j);
                }
            }

    这个循环了多少次呢!n*n次,时间复杂度为O(n^2):平方复杂度。

    百度百科对时间复杂度的定义是:在计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。

    我们再把常见的复杂度列举出来看看。

            int j = 0;
            for (int i = 0 ; i < n ; i++) {
                i = i * 2;
                j++;
                System.out.println("第几次"+j);
            }

    这个循环了多少次呢!假设我们把次数设为x,那2^x<n,解得次数x=log(n),时间复杂度为O(log(n)):对数。

            for (int i = 0 ; i < Math.pow(2,n); i++) {
    
                System.out.println("第几次"+i);
            }

     这个循环了多少次呢!2^n次,时间复杂度为O(2^n):指数复杂度。

    空间复杂度

    空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。

    简单的讲就是包括下面几部分。

    1.存储算法本身所占用的存储空间。

    2.算法的输入输出数据所占用的存储空间。

    3.算法在运算过程中临时占用的存储空间这三个方面。

    int a[] = new int[n];

    这个例子的空间复杂度是多少呢?这个数组开辟的空间是多少呢? O(n)。

    总结

    时间复杂度和空间复杂度本就是一个相互博弈的过程,一个多另一个就少,根据适当的问题,找到适当的解,这才是好办法。

    下面给一张常见数据结构时间和空间复杂度的图作为结尾把。

    展开全文
  • 程序时考虑优化程序的时间复杂度。 n 越大,优化效果越明显。 以 1 累加到 n 为例: 1.累加计算: int sum = 0; for (int i = 1;i <= n;i++) { sum += i; } 时间复杂度和 n 线性相关,所以为

    Big O notation

    O(1) 常数复杂度
    O(log n) 对数复杂度
    O(n) 线性复杂度
    O(n ^2)	平方
    O(n ^3)	立方
    O(2 ^n)	指数
    O(n!) 阶乘
    

    一段代码根据 n 的不同情况会运行多少次。

    时间复杂度

    写程序时考虑优化程序的时间复杂度。
    n 越大,优化效果越明显。

    以 1 累加到 n 为例:
    1.累加计算:

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

    时间复杂度和 n 线性相关,所以为 O(n)。

    2.公式计算:

    sum = n * (n+1) /2
    

    时间复杂度是常数,该代码块在运行时只会执行一次,所以为 O(1)。

    递归条件下的时间复杂度

    递归状态的递归树

    以斐波那契数列为例:

    int fib(int n) {
        if (n <= 2) {
    	return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }
    

    其时间复杂度为 2^n。

    此时间复杂度显然不是最优,递归树的画法和斐波那契问题的优化可以看看这篇文章:
    如何让递归的斐波那契数列跑的更快

    时间复杂度的通用计算方法:Master Theorem

    常见算法时间复杂度:

    • 二分查找 O(log n)
    • 二叉树遍历 O(n)
    • 图的遍历 O(n)
    • 归并排序 O(n log n)
    • 搜索算法:DFS、BFS O(n)

    空间复杂度

    1.数组的长度
    一般数组的最大长度,就是其对应的空间复杂度

    2.递归的深度

    展开全文
  • 关于时间复杂度的计算理解前言一、循环的 判定条件 没有主体变量... 所以,求一代码的时间复杂度,就是 得到关于次数 t 的多项式,再去掉常数和保留最高次方即可。 然而,求出 t 并不是那么容易的。要懂得如何从代


    前言

    如果代码的执行最多总次数可以被表示为一个多项式。
    那么时间复杂度就是

       保留最高次方、且去掉常数。
    之后的结果。 所以,求一段代码的时间复杂度,就是 得到关于次数 t 的多项式,再去掉常数和保留最高次方即可。


    然而,求出 t 并不是那么容易的。要懂得如何从代码中提取出 t 的多项式。
    主要分为以下两种题型:


    一、循环的 判定条件 没有主体变量的参与

    此类问题的又可分为两种类型

    1.1 非递归程序

    1.1.1 最基础类型

    for(int i = 0; i < n; ++i)
    	for(int j = 0; j < n; ++j)
    		for(int k = 0; k < 2; ++k)
    			A[i][j] = 100;
    
    for(int i = 0; i < n; ++i)
    		cout << "999" << endl;
    

    第一段代码是三层循环嵌套,第二层代码是一层循环。
    可以轻易的看出,
     第一段代码最内层的语句最多执行 2n22n^2 次.
     第二段代码最内层最多执行 n 次
    所以此段代码的 最多情况下的总执行次数为 2n2+n2n^2+n 次,
    若记执行次数为, 则
    t<=2n2+n t <= 2n^2+n
    根据 “留高次,去常数” 的原则, 0<t<=n20 < t <= n^2.
    用 “大 O 表示法” 记为
    O(2n2+n) O(2n^2 + n)
    但是当 nn\to\infty 时, 后面的低次项 n 与常系数 2 就显得微不足道了。所以为了更简洁的描述与比较快慢,可记为
    O(n2) O(n^2)

    1.1.2 迷惑类型

    还是刚刚的那段代码,只不过做了些许的改动。就足以让很多同学迷惑

    for(int i = 1; i <= n; ++i)
    	for(int j = 1; j <= i; ++j)
    		for(int k = 0; k < 2; ++k)
    			if(A[i][j] > 999)
    				A[i][j] = 100;
    
    for(int i = 0; i < n; ++i)
    		cout << "999" << endl;
    

    可以看出,此程序执行次数最多可能的语句还是 第一层循环的最内层语句

    				A[i][j] = 100;
    

    这样的语句我们称为 主体语句
    所以根据 留最高, 去常数。原则,我们只关心主体语句的执行过程,而不用去管第二个循环。此时代码简化为:

    for(int i = 1; i <= n; ++i)
    	for(int j = 1; j <= i; ++j)
    		for(int k = 0; k < 2; ++k)
    			if(A[i][j] > 999)
    				A[i][j] = 100;
    

    又,第三个循环的作用不过是给执行次数 t 的多项式添上系数 2 而已,所以也可以去掉。

    for(int i = 1; i <= n; ++i)
    	for(int j = 1; j <= i; ++j)
    		if(A[i][j] > 999)
    		  A[i][j] = 100;
    

    为什么不去掉 判断语句 呢??因为我们期望得到主体语句的最高执行次数,所以期待每次 判断语句 都会执行。所以在判断复杂度的时候,所以此时可以忽略判断语句。
    即:

    for(int i = 1; i <= n; ++i)
    	for(int j = 1; j <= i; ++j)
    		A[i][j] = 100;
    

    此时有两种方法解决这个问题:

    1.1.2.1 猜测+验证法

    第一个循环从 0到n-1 共会执行 n 次
    而对于第二个循环对的执行次数取决于第一个循环。

    但在最多情况下,
    也就是 i = n 时,
    第二个循环也会执行到 j = n.
    此时两个循从 1 到 n 都执行了 n 次. 所以复杂度依然为 nn=O(n2)n \cdot n = O(n^2)

    1.1.2.2 级数求和

    在这里插入图片描述

    众所周知,当 i = n 时,j所在的循环会执行n次,其中每一次都会使主体语句执行 1, 2 … n 次。
    次数如上表所示,所以总执行次数为
    在这里插入图片描述
    留最高, 去常数。后,为 O(n2)O(n^2)

    1.2 递归程序

    1.2.1 代入法

    T(n)={1,n=1,2T(n/2)+n,n>1. T(n)=\left\{ \begin{aligned} & 1 & , & n=1, \\ 2T(n/2)+n & , & n>1. \end{aligned} \right.
    此类问题分四步走:

    1. 写 T(n) 的迭代式(一直文本替换迭代下去)。
    2. 对每次迭代标号,从1到m。
    3. 利用 m 与递归截至条件的关系式 解出 m, 代回迭代式。
    4. 留最高,去常数。
      在这里插入图片描述

    1.2.2 主定理法

    1.2.3 递归树法

    二、循环的 判定条件 有主体变量的参与

    例题如下:

    在这里插入图片描述
     我们可以观察到:主体语句执行多少次 取决于 绿色框的值 是否符合循环的判定条件

    此时,我们是无法得知主体语句的循环次数 t 到底是多少的。
    这是由于主体语句的循环与否,是取决于循环条件的。
     如果满足判定条件,则主体语句循环,循环次数增加。
    此类题的解题步骤一般分为 4 步:

    1. 列出 主体语句的执行次数绿色框值 的表格
      以第一个为例:
      在这里插入图片描述

    2. 建立 F(t) 方程
        其中自变量 t 为 主体语句的执行次数,因变量为 绿色框值

    3. 将 F(t) 代回循环中的判定条件式,解出 t 变量。
        以第一个为例:

    n(t+1)2nt2+tnt+t n \geqslant (t+1)^2 \\ \Rightarrow n \geqslant t^2 + t \\ \Rightarrow \sqrt{n} \geqslant t + \sqrt{t}
    4. 留高次,去常数
    tnO(n) t \leq \sqrt{n} \\ 时间复杂度为 O(\sqrt{n})


    展开全文
  • 人们之所以花大力气去评估算法的时间复杂度和空间复杂度,其根本原因是计算机的运行速度和空间都是有限的。 在运行一段程序时,不仅要执行各种运算指令,同时还需要存储临时的中间数据,以便后面的程序可以继续执行...
  • 学习了一下如何计算时间复杂度

    千次阅读 2007-09-21 12:09:00
    (1)设n为正整数,利用大"O"记号,将下列程序段的执行时间表示为n的函数。 i=1; k=0 while(i{ k=k+10*i;i++;} 解答:T(n)=n-1, T(n)=O(n), 这个函数是按线性阶递增的。(2) x=n; // n>1 while (x>=(y+1)*(y+1))y++;...
  • 初探时间复杂度

    2018-06-14 17:23:57
    算法的复杂度分为时间复杂度和空间复杂度,...如何计算一个算法的时间复杂度? 为什么要引入时间复杂度? 来看一非常简单的代码 public static void main(String[] args) { int n = 100; for (int ...
  • 一般而言,代码执行过程中会消耗计算时间和计算空间,那需要衡量就是时间复杂度和空间复杂度 这代码对于资源消耗是多少 我们不会关注这代码对于资源消耗绝对量,因为不管是时间还是空间,它们消耗...
  • 时间复杂度是学习算法的基石,也是判断一个算法优劣的重要因素,今天我们来聊聊什么是时间复杂度以及如何去算一个算法的时间复杂度。 本文以C++语言为例 1.电脑运行程序是需要时间的 void print() { //这代码会...
  • 时间复杂度

    2018-04-27 17:51:40
    算法效率衡量执行时间反应算法效率对于同一问题,我们给出了两种解决算法,在两种算法的实现中,我们对程序执行的时间进行了测算,发现两段程序执行的时间相差悬殊(214.583347秒相比于0.182897秒),由此我们可以...
  • 衡量算法效率的标准:... 接下来通过两代码来说明下如何计算一个程序的时间复杂度以及空间复杂度:int SumMemory(int n) // 时间复杂度:共执行2n+5次,用大O表示法记为O(n);空间复杂度:4n+12字节,用大O表示法...
  • 时间复杂度与“大O记法”如何理解“大O记法”最坏时间复杂度时间复杂度的几条基本计算规则 1.4. 算法效率衡量 算法效率衡量 执行时间反应算法效率 对于同一问题,我们给出了两种解决算法,在两种算法实现中,我们...
  • a) 耗时长短:通常我们可以运行该算法程序,根据其运行时间的长短确定耗时,耗时少则性能好,但是由于不同计算机cpu计算能力不同(当然还有其他很多因素,比如cpu时间片占用导致我们算法等待),所以用这种算法...
  • 算法复杂度

    2018-11-09 00:28:00
    算法和数据结构密不可分。算法依赖数据结构。 数据结构和算法解决是“如何让计算机更快时间、更省空间解决问题” 因此从 执行时间 和 资源占用 两个维度来...比如一段程序,我们如何估算这代码执行时间? ...
  • 对于同一问题,我们给出了两种解决算法,在两种算法的实现中,我们对程序执行的时间进行了测算,发现两段程序执行的时间相差悬殊,由此我们可以得出结论:实现算法程序的执行时间可以反映出算法的效率,即算法的优劣...
  • 算法复杂度分析

    2018-12-14 15:03:37
    分别从时间复杂度和空间复杂度两个概念来描述性能问题,而者统称为复杂度。 复杂度描述是算法执行时间(或占用存储空间)与数据规模增长关系。 为什么要进行复杂度分析 有人说我可以通过把程序跑一边,...
  • 对于同一问题,我们给出了两种解决算法,在两种算法的实现中,我们对程序执行的时间进行了测算,发现两段程序执行的时间相差悬殊(214.583347秒相比于0.182897秒),由此我们可以得出结论:实现算法程序的执行时间...
  • 精确计算程序效率

    2012-07-26 20:49:36
    在程序和算法设计过程中,我们经常面临两个问题...那么如何计算程序的执行时间呢?下面写出一般的程序来计算执行一程序所需的时间。 #include #include void main() { clock_t start,finish; double
  • 如何进行复杂分析(1) 大O表示法(2) 3种时间复杂度分析方法(3) 常见的时间复杂度(4) 空间复杂度(5) 如何熟练4 复杂度分析的4个概念4.1 最好,最坏,平均和均摊4.2 为什么引入4个概念4.3 平均和均摊复杂度计算5 课后...
  • 如何学好编程?学习经验汇总

    千次阅读 2017-06-09 20:36:50
    标题 量产型炮灰程序员 ...计算段程序的时间复杂度、空间复杂度,如何理解栈、队列等数据结构,了解网络协议的基础。中级SICP进阶高级统筹学习代码的历程,你会发现都是类似的,是螺旋上升的,
  • 代码效率优化方法论

    2020-07-12 23:51:15
    代码效率优化方法论复杂度:如何衡量程序运行的效率数据结构:将“昂贵”的时间复杂度转换成“廉价”的空间复杂度 复杂度:如何衡量程序运行的效率 复杂度是什么 复杂度是衡量代码运行效率的重要的度量因素。在...
  • 常见算法

    2020-04-02 12:03:51
    ​ 答:用time模块来判断,time.time()来进行计算,前提是两段程序必须运行在同一个硬件相同(cpu)环境下,才会有意义 因此,我们使用时间方式来衡量一个程序是否快慢没有任何意义。所以使用程序执行大概...
  • 计算循环队列元素个数:“尾指针减头指针”,若为负数,再加其容量即可。 1.5 链表 在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,称为数据域;另一部分用于存放指针,称为指针域。其中...
  • 前言:编辑距离此题为LeetCode第72号题,本质上可以采用动态规划DP方法求解,但是在求解时候理解出现了问题,导致懵逼了一段时间,还好终于想通了,现将自己理解思路、程序实现以及空间复杂度优化整理如下,...
  • 数据结构和算法就是解决这两个问题,如果要设计出好的程序就必须知道如何去衡量一代码好坏,也就是做复杂度分析。 1、 时间复杂度   先来看看时间复杂度的定义: 一般情况下,算法中基本操作重复执行...
  • 笔者前段时间为线上业务实现了一个与内容结构非耦合文本高亮笔记功能。非耦合是指不需要为高亮功能建立特殊页面 DOM 结构,而高亮功能对业务近乎透明。该功能核心部分具有较强通用性与移植性,故...
  • 文章目录算法引入方法1--效率低方法2算法效率衡量时间复杂度最坏时间复杂度计算规则 算法引入 方法1–效率低 算法:面对问题时,将我们思路用计算机程序写出来,告诉计算机怎么做,如何让计算机运行将题解答...

空空如也

空空如也

1 2 3
收藏数 54
精华内容 21
关键字:

如何计算程序段的时间复杂度