网站 建设 开发 协议,怎么做二手网站代理,如何在阿里云做网站,餐饮食材配送网站开发企划书作者 | OverRedMaple责编 | Carol来源 | CSDN 博客封图 | CSDN付费下载于东方 IC如果你还在发愁究竟怎么计算时间复杂度和空间复杂度#xff0c;那你是来对地方了#xff01;名词解释#xff1a;在计算机科学中#xff0c;时间复杂性#xff0c;又称时间复杂度#xff0c… 作者 | OverRedMaple责编 | Carol来源 | CSDN 博客封图 | CSDN付费下载于东方 IC如果你还在发愁究竟怎么计算时间复杂度和空间复杂度那你是来对地方了名词解释在计算机科学中时间复杂性又称时间复杂度算法的时间复杂度是一个函数它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述不包括这个函数的低阶项和首项系数。使用这种方式时时间复杂度可被称为是渐近的亦即考察输入值大小趋近无穷时的情况。时间复杂度的表示方法其实就是算法代码的执行效率算法代码的执行时间。我们来看下面一个简单的代码int sumFunc(int n) { int num 0; // 执行一次 for (int i 1; i n; i) { // 执行n次 num num i; // 执行n次 } return num;}
假设每行代码的执行时间为t那么这块代码的时间就是(2n2)*t由此得出代码执行时间T(n)与代码的执行次数是成正比的那么我们来看下一个例子int sumFunc(int n) { int num 0; // 执行一次 for (int i 1; i n; i) { // 执行n次 for (int j 1; j n; j) { //执行n*n次 num num i * j; // 执行n*n次 } }}
同理该代码执行时间为(2n*nn1)*t没意见吧继续往后看注意在数据结构/算法中通常使用T(n)表示代码执行时间n表示数据规模大小f(n)表示代码执行次数综合所以上面这个例子可以表示为f(n)(2n*nn1)*t其实就是一个求总和的式子O(大写O)表示代码执行时间与 f(n) 成正比例。根据上面两个例子得出结论代码的执行时间 T(n)与每行代码的执行次数 n 成正比人们把这个规律总结成这么一个公式 T(n) O(f(n))所以呢第一个例子中的 T(n)O(2n1)第二个例子中的 T(n)O(2n*nn1)这就是时间复杂度表示法也叫大O时间复杂度表示法。但是大O时间复杂度并不具体表示代码真正的执行时间而是表示代码执行时间随数据规模增长的变化趋势所以也叫作渐进时间复杂度简称时间复杂度。与泰勒公式相反的是算了扯哪去了…当n变得越来越大时公式中的低阶常量系数三部分影响不了其增长趋势所以可以直接忽略他们只记录一个最大的量级就可以了所以上述两个例子实际他们的时间复杂度应该记为T(n)O(n) T(n)O(n*n)我想你应该明白大致是怎么回事了那么我们来看看如何去计算它时间复杂度的分析与计算方法1循环次数最多原则我们上面说过了当n变得越来越大时公式中的低阶常量系数三部分影响不了其增长趋势可以直接忽略他们只记录一个最大的量级就可以了。因此我们在计算时间复杂度时只需关注循环次数最多的那段代码即可。int sumFunc(int n) {int sum 0; //执行1次忽略不计for (int i 0; i n; i) {sum i; // 循环内执行次数最多执行次数为n次因此时间复杂度记为O(n)} return sum; //执行1次忽略不计
}
2加法原则int sumFunc(int n) {int sum 0; //常量级忽略for (int i 0; i 99; i) {sum i; //执行100次还是常量级忽略}for (int i 0; i n; i) {sum i; //执行n次}for (int i 0; i n; i){for (int j 0; j n; j) {sum i; //执行n*n次}}return sum;
}
上述例子中最大的两块代码时间复杂度分别为 O(n)和O(n*n)其结果本应该是T(n)O(n)O(n*n)我们取其中最大的量级因此整段代码的复杂度为O(n * n)所以得出结论量级最大的那段代码时间复杂度总的时间复杂度3乘法原则嵌套代码的复杂度等于嵌套内外代码复杂度的乘积void Func1(int n) {for (int i 0; i n; i) {Func2(n); //执行n次每次都会调用Func2函数执行n次}
}
void Func2(int n) {int sum 0;for (int i 0; i n; i){sum 1; //执行n次}
}
因此这段代码时间复杂度为O(n) * O(n) O(n*n) O(n*n)同理如果将其中一个n换成m那么它的时间复杂度就是O(n*m)常见的几种时间复杂度1O(1)常量级时间复杂度void Func(void) {for (int i 0; i 100; i) {printf(hello); //执行一百次也是常量级记为O(1)}
}
void Func(void) {printf(hello);printf(hello); printf(hello);//各执行一次还是记为O(1)
}
相信你也看明白了O(1)不是说代码只有一行这个1它代表的是一个常量即使它有以前一万行这样的也是O(1)因为它是固定的不会变化也就是常量所以凡是常量级复杂度代码均记为O(1)2常见的O(n)复杂度void Func(int n) {for (int i 0; i n; i) {printf(hello);}
}
不用多说了吧继续3O(logn)O(nlogn) 这就有点难度了首先我们来回忆以下换底公式记住公式啊来看例子void Func(int n) {for (int i 1; i n; i) {i i * 2;}
}
可以看出i i * 2这行代码执行次数是最多的那么到底执行了多少次呢第一次 i2执行第二次 i4执行第三次 i8…假设它执行了x次那么x的取值为当上述代码的2改成3的时候x的取值也就是当然不管log的底数是几是e也好是10也罢统统记为这是为啥子念由换底公式可以计算出换底之后可以看出log3(2)其实就是一个常数忽略它而在这场游戏中log默认就是以2为底的所以统统记为O(logn)。void Func(int n) {for (int i 0; i n; i) {Func2(n); //执行n次嵌套调用每次调用执行logn次}
}
void Func2(int n) {for (int i 0; i n; i){i i * 2; //执行logn次}
}
所以这个O(nlogn)也很好理解了吧其他就不赘述了相信聪明的你一定可以举一反三如果对你有帮助就点个“在看”支持下作者吧《原力计划【第二季】- 学习力挑战》正式开始即日起至 3月21日千万流量支持原创作者更有专属【勋章】等你来挑战推荐阅读BZip2Codec压缩、Map端压缩控制、Reduce端压缩控制……都在这份Hadoop整合压缩知识点里了
Linux 会成为主流桌面操作系统吗
打开容器世界的大门Docker、POD 初探
乔布斯遗孀裸捐 250 亿美元财产没兴趣累积财富
号称3个月发布最强量子计算机卖口罩的霍尼韦尔凭什么
闪电网络的 5 个优点和4 个缺点、本质、来源与工作原理……一文带你读懂闪电网络
真香朕在看了
