-
时间复杂度和空间复杂度分析
2021-01-17 22:08:28如何评价一段代码或算法的性能和好坏?目前衡量代码质量的指标主要有两个:分别为时间复杂度和空间复杂度。其中时间复杂度指的是执行当前算法所消耗的时间,空间复杂度指的是指执行当前算法需要占用多少内存空间。有...如何评价一段代码或算法的性能和好坏?目前衡量代码质量的指标主要有两个:分别为时间复杂度和空间复杂度。其中时间复杂度指的是执行当前算法所消耗的时间,空间复杂度指的是指执行当前算法需要占用多少内存空间。有的时候时间和空间是不可兼得的,需要从中去取一个平衡点。下面简单描述一下如何计算时间复杂度和空间复杂度
一、时间复杂度
利用大O符号表示法来表示时间复杂度,即T(n) = O(f(n))。其中f(n) 表示每行代码执行次数之和,而 O 表示正比例关系,这个公式的全称是:算法的渐进时间复杂度。
for(i=1; i<=n; ++i) { j = i; j++; }
(1+n+n)*time :T(n) = O(n) 。因为大O符号表示法并不是用于来真实代表算法的执行时间的,它是用来表示代码执行时间的增长变化趋势的。假设n为无穷大时,倍数2和加数1可以忽略不计。
目前常见的时间复杂度量级有以下几种,按照顺序时间复杂度越来越大,执行的效率越来越低:
(1)常数阶O(1); (2)对数阶O(logN); (3)线性阶O(n); (4)线性对数阶O(nlogN);
(5)平方阶O(n²); (6)立方阶O(n³); (7)K次方阶O(n^k); (8)指数阶(2^n)。
下面主要介绍几种常见的时间复杂度计算案例:
1、常数阶O(1)
k=i; i=j; j=k; j++;
2、对数阶O(logN)
int i = 1; while(i<n) { i = i * 2; }
上面的代码可以发现循环并不是到n结束,因为i的值在变化,i每次都在乘以2,2^x=n为终止条件,此时x也就为logN。
3、线性阶O(n)
for(i=1; i<=n; i++) { j = i; j++; }
4、线性对数阶O(nlogN)
for(m=1; m<n; m++) { i = 1; while(i<n) { i = i * 2; } }
5、平方阶O(n²)
for(x=1; i<=n; x++) { for(i=1; i<=n; i++) { j = i; j++; } }
时间复杂度为 O(n²)。
for(x=1; i<=m; x++) { for(i=1; i<=n; i++) { j = i; j++; } }
时间复杂度为 O(m*n)。
二、空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势,我们用 S(n) 来定义。空间复杂度比较常用的有:O(1)、O(n)、O(n²)。
1、空间复杂度 O(1)
如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)。
int i = 1; int j = 2; ++i; j++; int m = i + j;
代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)。
2、空间复杂度 O(n)
int[] m = new int[n] for(i=1; i<=n; ++i) { j = i; j++; }
这段代码中,第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2-6行,虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)。
3、空间复杂度O(N2)
int[][] arr = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { arr[i][j] = new Random().nextInt(); } }
随着数据量的变化,内存消耗为平方变化。
-
最好、最坏、平均、均摊时间复杂度分析
2018-11-20 01:50:53有时候我们分析一段代码的时间复杂度时,并不能很直观的就得出结果,需要结合具体的场合来判断它的平均情况。下面来看一个栗子: /** * 找出给定数组中给定元素的位置,如果找不到返回-1 * @param arr 给定数组...1.最好、最坏、平均情况时间复杂度
有时候我们分析一段代码的时间复杂度时,并不能很直观的就得出结果,需要结合具体的场合来判断它的平均情况。下面来看一个栗子:
/** * 找出给定数组中给定元素的位置,如果找不到返回-1 * @param arr 给定数组 * @param target 给定元素 * @return */ public int find(int[] arr, int target) { int n = arr.length; for (int i = 0; i < n; i++) { // 依次遍历数组,如果找到和目标元素相同的值,在返回该值所在下标 if (arr[i] == target) { return i; } } return -1; }
该栗子是在给定数组中寻找给定元素的位置,如果找到返回下标,结束循环;如果找不到则返回-1。
那么这段代码时间复杂度是多少呢?这就不好直接判断了,因为目标元素在数组中位置的不同导致时间复杂度的不同。针对上面这段代码,时间复杂度分析如下:
1.最好情况时间复杂度:目标元素刚好在数组第一个位置,那么只需要一次就能找到,时间复杂度很明显是常量阶O(1)。
2.最坏情况时间复杂度:目标元素在数组最后一个位置或者不在数组中,那么得需要遍历完整个数组才能得出结果,时间复杂度为O(n)。
最坏情况运行时间是一种保证,那就是运行时间不会再坏了。在应用中,这是一种最重要的需求,通常,除非特别指定,我们提到的运行时间都是最坏情况运行时间。
可以看出来,由于目标元素的位置不同,导致时间复杂度出现量级差异。这种情况下就需要考虑平均情况时间复杂度,下面简单分析下:目标元素如果在数组中,出现的位置有n种情况,加上不在数组中这一种情况,总共n+1种情况。每种情况下需要遍历的次数如下表:
目标元素所在位置与遍历次数的关系 第1个位置 遍历1次 第2个位置 2次 第3个位置 3次 第n个位置 n次 不在数组中 n次 由上表可以得出平均遍历次数=各种情况遍历次数相加÷总的情况数。
即遍历次数f(n)与数据规模之间的关系为:
根据大O分析法,忽略低阶项和系数得,T(n) = O(f(n)) = O(n)。所以平均情况时间复杂度为O(n)。
平均情况时间复杂度是所有情况中最有意义的,因为它是期望的运行时间。
2.均摊时间复杂度
均摊时间复杂度对应的分析方法叫摊还分析。下面还是以具体的栗子来说明:
/** * ${向数组中插入元素,如果数组已满,扩容为原来的2倍} * * @author WangXiaoLong * @version 1.0 * @create 2018-11-20 0:25 */ public class IntArray { // 记录数组中已有元素个数 int count = 0; // 声明数组 int[] arr; public IntArray(int n){ // 初始化数组,这里只是举例说明,不考虑n<0等异常情况 arr = new int[n]; } /** * 插入元素 * @param value */ public void insert(int value) { // 数组已经存满,进行扩容操作,然后将之前的元素拷贝到新数组中 if (count >= arr.length) { // 新建一个大小为之前数组2倍的新数组 int[] arr2 = new int[2*arr.length]; // 将之前数组中元素copy到新数组中 for (int i = 0;i<arr.length;i++) { arr2[i] = arr[i]; } // 将新数组赋值给原数组(扩容后的数组代替原来的数组) arr = arr2; } // 数组没满,直接将值插入到数组中即可 arr[count] = value; count++; } }
上面模拟了数组动态扩容的场景,假如数组元素已满,再插入时就新建一个长度为原数组2倍的数组,然后把原数组中的值copy到新数组中,将新数组替换为原数组。化成图解如下:
可以分析出来,当数组没满时,插入操作很快,只需要执行1次赋值操作即可,时间复杂度为O(1)。当数组已满,需要扩容为原来的两倍,然后将元素数组中的值拷贝到新数组中,假如原数组长度为n,则需要进行n此操作,时间复杂度退化为O(n)。
如果细心观察可以发现,每当经历n次时间复杂度为O(1)的操作时,便经历1次时间复杂度为O(n)的操作,有一定的时序规律,并且出现高级别复杂度的情况极少。我们将出现高级别的情况均摊到低级别复杂度的情况中,整个插入操作的时间复杂度就变为O(1)了。这就是摊还分析的大致思想。
总结:
1.代码在不同情况下复杂度出现量级差别,则用平均情况时间复杂度分析。
2.代码在绝大多数情况下是低级别复杂度,只有极少数情况是高级别复杂度,并且具有一定的时序规律,则用均摊时间复杂度分析。
-
算法之时间复杂度
2020-02-17 22:16:22时间复杂度分析有下面几个原则: 1)只关注循环执行次数最多的一段代码; 2)加法原则:总复杂度等于量级最大的那段代码的复杂度。用公式表示即为:T1(n) = O(f(m)),T2(n) = O(g(n)),T1(n) + T2(m) = O(max(f(n)...1、时间复杂度分析有下面几个原则:
1)只关注循环执行次数最多的一段代码;
2)加法原则:总复杂度等于量级最大的那段代码的复杂度。用公式表示即为:
T1(n) = O(f(m)),T2(n) = O(g(n)),T1(n) + T2(m) = O(max(f(n), g(m)))
;3)乘法原则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘机。用公式表示即为:
T1(n) = O(f(m)),T2(n) = O(g(n)),T1(n) * T2(m) = O(f(n) * g(m))
2、常见的时间复杂度有以下几种:
1)常量阶:
O(1)
2)对数阶:
O(logn)
3)线性阶:
O(n)
4)线性对数阶:
O(nlogn)
5)平方阶:
O(n ^ 2)
6)指数阶:
O(2 ^ n)
7)阶乘阶:
O(n!)
其中,1)-5)为多项式量级;6)、7)为非多项式量级,所对应的算法问题被称为非确定多项式问题(NP 问题,Non-Deterministic Polynomial)。
3、常用的时间复杂度按照耗费的时间从小到大依次是:
O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)
n logn √n nlogn n² 2ⁿ n! 5 2 2 10 25 32 120 10 3 3 30 100 1024 3628800 50 5 4 250 2500 约10^15 约3.0*10^64 100 6 10 600 10000 约10^30 约9.3*10^157 1000 9 31 9000 1000 000 约10^300 约4.0*10^2567 从上表可以看出,O(n)、O(logn)、O(√n )、O(nlogn )随着n的增加,复杂度提升不大,因此这些复杂度属于效率高的算法,反观O(2ⁿ)和O(n!)当n增加到50时,复杂度就突破十位数了,这种效率极差的复杂度最好不要出现在程序中,因此在动手编程时要评估所写算法的最坏情况的复杂度。
4、示例代码
#include <stdio.h> #include <stdlib.h> #include <time.h> int main() { time_t c_start, c_end; unsigned long long n=100,sum=0; //线性阶 c_start = clock(); for(unsigned long long i=0;i<n;i++){ sum++; } c_end = clock(); printf("[线性阶]运算次数:%lld,耗时: %f s \n",sum,difftime(c_end,c_start) / CLOCKS_PER_SEC); //对数阶 c_start = clock(); unsigned long long i=1; sum=0; while(i>0 && i<n){ i=i*2; sum++; } c_end = clock(); printf("[对数阶]运算次数:%lld,耗时: %f s \n",sum,difftime(c_end,c_start) / CLOCKS_PER_SEC); //平方阶 c_start = clock(); sum=0; for(unsigned long long i=0;i<n;i++){ for(unsigned long long j=0;j<n;j++){ sum++; } } c_end = clock(); printf("[平方阶]运算次数:%lld,耗时: %f s \n",sum,difftime(c_end,c_start) / CLOCKS_PER_SEC); //立方阶 c_start = clock(); sum=0; for(unsigned long long i=0;i<n;i++){ for(unsigned long long j=0;j<n;j++){ for(unsigned long long k=0;k<n;k++){ sum++; } } } c_end = clock(); printf("[立方阶]运算次数:%lld,耗时: %f s \n",sum,difftime(c_end,c_start) / CLOCKS_PER_SEC); //指数阶2^n c_start = clock(); n=28; sum=0; for(unsigned long long i=0;i<(1<<n);i++){ sum++; } c_end = clock(); printf("[指数阶2^n]运算次数:%lld,耗时: %f s \n",sum,difftime(c_end,c_start) / CLOCKS_PER_SEC); //阶乘阶n! c_start = clock(); n=12; sum=0; unsigned long long multi=1; while(n>1){ multi = multi*n; n--; } while(multi>0){ sum++; multi--; } c_end = clock(); printf("[阶乘阶n!]运算次数:%lld,耗时: %f s \n",sum,difftime(c_end,c_start) / CLOCKS_PER_SEC); return 0; }
-
算法分析之【时间复杂度】
2020-02-01 13:05:15当电脑运行下面这段代码的时候,执行任何一条语句都需要花费时间(为了方便讨论,这里我们把每一条语句的执行时间都看做是一样的,记为一个时间单元) 这个程序有这么几个地方消耗了时间: ① 蓝色框的两条语句,...时间复杂度
当电脑运行下面这段代码的时候,执行任何一条语句都需要花费时间(为了方便讨论,这里我们把每一条语句的执行时间都看做是一样的,记为一个时间单元)
这个程序有这么几个地方消耗了时间:
① 蓝色框的两条语句,花费2个时间单元
② 黑色框的一条语句,花费n+1个时间单元
③ 红色框的两条语句,花费2*n个时间单元
那么一共花费了3n+3个时间单元,可以看出,程序消耗的时间和n成线性关系
- 用T(n)表示这个程序运行了多长时间,那么这个程序运行的时间就可以写成T(n)=3n+3。其中的n被我们称为问题的规模,其实就是处理的问题的大小
我们常常会对这个函数进行简化,使得它既简单又不失函数的主要特性
所以一般只关心随着问题规模n趋于无穷时函数中对函数结果影响最大的项,也就是最高次项举个栗子:
- T(n)=n+1 忽略常数项 :T(n)~n
- T(n)=n+n2 忽略低阶项: T(n)~n2
- T(n)=3n 忽略最高阶的系数: T(n)~n
至于判断哪个是高阶项,哪个是低阶项,只需记住下面的大小关系就行了,到时按照这个进行忽略(忽略相对较小的)
简化后的式子被称为这个程序算法的时间复杂度,记做O(f(n)),f(n)就是简化后的式子,比如说刚开始讨论的T(n)=3n+3,简化后T(n)~f(n)=n,那我们记为O(n)时间复杂度可以表示某个算法的运行时间的趋势,大致地度量算法效率的好坏
时间复杂度的计算
计算时间复杂度大O的方法
一、得出运行时间的函数
二、对函数进行简化- 用常数1来取代运行时间中所有加法常数
- 修改后的函数中,只保留最高阶项
- 如果最高阶项存在 且系数不为1,则忽略这个项的系数(即令其系数为1)
举个栗子:
int n = 0; n = n + 6; printf(n);
T(n)=3(三条语句1+1+1),对这个函数进行简化,用常数1取代常数3,然后取代后的函数没有最高阶项,那么这个算法的时间复杂度就是O(1).
O(1)也被称为常数阶
如果每次都要把时间函数算出来,挺麻烦的,可以耍耍小聪明,一般来说,最内层执行次数最多的语句就决定了整个算法的趋势for(int i = 0; i < n; i++) printf("哈");
这个内层打印语句需要循环n次,随着问题规模n的增加会呈线性增加,可以判定其时间复杂度为O(n)
按照这个方法就很容易得出下面这个嵌套的两层for循环的时间复杂度为O(n2)
for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cout << "平方阶" << endl; } }
有一个很神奇的函数——对数函数,它随着自变量的增大,因变量增长的很慢
下面这段代码的复杂度就为对数级别O(logn)int sum = 1; while(sum < n) { sum = sum * 2; }
和之前的分析方法一样,我们着重看执行次数最多的内层代码语句
sum = sum * 2;
每循环一次,sum就给自身乘以2,乘了多少次就跳出循环了呢(大于等于n)?不知道,就设为x吧,那么 2x=n,解出 x=log2n,这说明随着n的增大,最消耗时间的内层语句是呈对数变化的。
感谢阅读~
- 本文参考于:算法分析神器—时间复杂度
-
humble number的代码分析
2008-05-31 22:24:00前段时间在blog上写了一个humble number的代码,没有想到有热心读者坚持希望知道这个算法的实现原理,本着share的原则,今天我的作品中就来探讨一下关于这个算法是如何实现的。我们前面分析过,最笨的一种humble ... -
近年来,网络游戏和各类社交网络都在成几何倍数的增长,不管网络游戏还是各类互动社交网络,交互性和复杂度都在迅速提高,都需要在极短的时间内将数据同时投递给大量用户,因此传输技术自然变为未来制约发展的一个...
-
大话数据结构 —— 2.9.6 平方阶
2018-09-10 15:57:05所以这段代码的时间复杂度为0(n^2)。那如果有三个这样的嵌套循环呢? 没错,那就是n^3。所以我们很容易总结得出,循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。 例一:下面的例子是一个循环嵌套,... -
【716-Week 03】第一次全方位认识贪心算法
2020-11-24 16:19:30下面一段关于贪心算法的原理,出自《算法导论》贪心算法章节 贪心算法的一般性质: <ol><li>将最优化问题转化成这样的形式:对其做出一次选择后,只剩下一个子问题需要求解</li><li>证明... -
构建一个使用 Virtual-DOM 的前端模版引擎
2021-01-09 01:41:16</li><li>4.1 编译原理相关</li><li>4.2 模版引擎的EBNF</li><li>4.3 词法分析</li><li>4.4 语法分析与抽象语法树</li><li>4.5 代码生成</li><li> <ol><li>完整的 Virtual-Template</li></ol> </li><li> <ol><li>... -
做了一个小时的面试题(没有过 希望大家帮忙答下 虽然很幼稚 毕竟每个人都是这么过来的吗 感激了!...
2010-04-16 11:10:58通常这一组类有一个公共的抽象父类并且实现了相同的方法,但是这些方法针对不同的数据进行了不同的操作。 首先需要定义一个基类,该类的子类通过不同的方法实现了基类中的方法。 然后需要定义一个工厂类,工厂... -
Compiler_mean3tmp.rar
2019-05-16 23:27:36输出规约过程,很小一段语句可能就会很长的规约过程。 letex.LexResult.java 显示词法分析结果。输出全部识别出来的单词。 LR1识别实现完全在Parse3包里,自己看名字去读代码。 几乎每一个主要的类我都写了main()... -
格蠹汇编:软件调试案例集锦.张银奎(带详细书签).pdf
2018-04-26 23:11:14对于这几句“经文”中的格物致知,朱熹在他的名著《大学章句》中有一段非常好的诠释,摘录如下: 所谓致知在格物者,言欲致吾之知,在即物而穷其理也。盖人心之灵莫不有知,而天下之物莫不有理,惟于理有未穷,故其... -
软件工程-理论与实践(许家珆)习题答案
2011-01-12 00:49:42比较复杂的系统不能画在一张纸上,逐层分解的画法可以控制每一层的复杂度。 顶层:将整个系统作为一个加工,描述系统边界(输入与输出)。 中间层:表示某个加工分解为一组子加工,其中的子加工还需进一步分解。 ... -
2017数学建模国赛+深圳杯优秀论文
2018-10-30 19:03:46但是我已经具备了看到一大段代码,自己对其中的部分语句进行修改,为我 所用,实现自己想要的功能。对于建模比赛来说,达到这种水平一般来说是够用 了,只要在编程同学写程序的时候,建模的同学可以检查 MATLAB 代码... -
数据结构(C++)有关练习题
2008-01-02 11:27:182、 请用C++编写一个算法,完成以下功能: a. 从键盘输入一段文字,以$作结束符号; b. 统计文字中的文本行数,字母,数字以及其他符号的数量,并在屏幕上显示; 3、 请用C++编写一个算法,完成矢量的... -
计算机二级公共基础知识
2011-04-30 14:00:09② 每一个结点最多有一个前件,也最多有一个后件。 则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串等都为线性结构。 如果一个数据结构不是... -
C++程序员面试宝典
2013-04-01 13:36:19本书内容大多取材于各大IT公司的面试题,详细分析了应聘C/C++程序员职位的常见考点。本书主要内容包括:面试流程及准备、英语面试、电话面试、C/C++语言基础、流程控制、输入/输出、预处理、内存管理、指针、面向... -
webpack工程化打包原理解析与实现
2020-11-27 16:01:51首先一段代码转化成的抽象语法树是一个对象,该对象会有一个顶级的 type 属性 Program ,第二个属性是 body 是一个数组。body 数组中存放的每一项都是一个对象,里面包含了所有的对于该语句的描述信息 ... -
天猫前端基础技术体系MAP简介
2021-01-10 03:54:06前端这个行业本身易入门难精通的一部分原因也是每一次的技术深入都需要技术广度上有提升,这些广度以前覆盖了HTTP、其他后端语言、操作系统、印刷设计等,现在由于移动设备的兴起,广度要求的点做... -
c语言编写单片机技巧
2009-04-19 12:15:17答:一般在8位单片机与ARM方面的嵌入式系统是有层次上的差别,ARM适用于系统复杂度较大的高级产品,如PDA、手机等应用。而8位单片机因架构简单,硬件资源相对较少,适用于一般的工业控制、消费性家电等等。对于一个...
-
系统设计:准备系统设计面试问题-源码
-
2021年 系统分析师 系列课
-
Liunx 优化思路与实操步骤
-
linux中安装nacos,seata并集成到nacos中
-
v-for的用法
-
php底层运行机制与原理
-
浅谈数据仓库建设中的数据建模方法
-
mac 配置php-fpm
-
项目已启动但浏览器前端按钮无反应
-
能扫描任意函数图像的光扫描器
-
jquery使用serialize()出现中文乱码怎么办
-
大尺寸薄壳物体表面的三维光学自动检测
-
深究字符编码的奥秘,与乱码说再见
-
物联网基础篇:快速玩转MQTT
-
猫眼谐振腔在全外腔长氦氖激光器中的应用
-
平面型四光纤耦合系统的研究
-
PHP超全局变量
-
51单片机60秒倒计时 数码管显示
-
货币转换微服务:使用Spring Cloud的货币转换微服务-源码
-
基于python的dango框架购物商城毕业设计毕设源代码使用教程