溧阳市住房和城乡建设局网站,宁波网页设计的技术要求,百度快照网站,上海工商网上企业查名#x1f413; 时间复杂度
常用排序的时间复杂度 时间频度 算法需要花费的时间#xff0c;和它语句执行的次数是成正比的#xff0c;所以会把一个算法种语句执行次数称为语句频度和时间频度、记作T(n)。 定义
时间复杂度就是找到一个无限接近时间频度T(n)同数量级的函数 时间复杂度
常用排序的时间复杂度 时间频度 算法需要花费的时间和它语句执行的次数是成正比的所以会把一个算法种语句执行次数称为语句频度和时间频度、记作T(n)。 定义
时间复杂度就是找到一个无限接近时间频度T(n)同数量级的函数当n趋近于无穷大时Tn)/f(n)的极限值为不等于零的常数则称f(n)是T(n)的同数量级函数。记作T(n)O(f(n)),称O(f(n)) 为算法的渐进时间复杂度 通俗一点就是找到一个和T(n)同一量级的函数F(n),写作O(f(n)),一般在程序中我们会看最内层或者说其执行次数最多的代码行。 时间复杂度计算
时间复杂度中O是受T(n)种n变化次数最多的那一项影响比如T(n) n^3n^2n23 那这个最大的影响项就是O( n^3)
常见的时间复杂度
阶数
执行次数函数举例阶非正式术语12O(1)常数阶2n3O(n)线性阶n^22n1O(n^2)平方阶5log2n20O(logn)/log2n对数阶2n3nlog2n19O(nlogn)nlogn阶n^3n^23n4O(n^3)立方阶2^nO(2^n)指数阶
大小排序
消耗时间从小到大 O(1) O(logn) O(n) O(nlogn) O(n^2) O(n^3) O(2^n) O(n!) O(nn) 实例
常数阶O(1) 没有任何循环等复杂结构时间复杂度就是O(1)常量阶 代码示例
int a 1; //O1
int b 1; //O1
int t a b; //该行执行了O1次故O1对数阶O(log₂n) 在while循环里面每次都将 i 乘以 2乘完之后i 距离 n 就越来越近了。假设循环x次之后i 就大于 2 了此时这个循环就退出了也就是说 2 的 x 次方等于 n那么 x log2n也就是说当循环 log2n 次以后这个代码就结束了。因此这个代码的时间复杂度为O(log2n) 代码示例
int i 1;
while (i n){i i * 2; //该行执行了O(log2n)次故O(log2n)
}线性阶O(n) for循环里面的代码会执行n遍因此它消耗的时间是随着n的变化而变化的因此这类代码都可以用O(n)来表示它的时间复杂度。 代码示例
for (int i 1; i n; i) {System.out.println(1); //该行执行了O(n)次故O(n)
}线性对数阶O(nlog₂n) 线性对数阶O(nlogN) 其实非常容易理解将时间复杂度为O(logn)的代码循环N遍的话那么它的时间复杂度就是 n * O(logN)也就是了O(nlogN)。 代码示例 for (int i 1; i n; i) { //该循环执行了n次int j 1;while (jn){j j * 2; //该行执行了O(nlog2n)次故O(nlog2n)}}平方阶O(n²) 平方阶O(n²) 就更容易理解了就是两层n的循环嵌套如果把 O(n) 的代码再嵌套循环一遍它的时间复杂度就是 O(n²)这段代码其实就是嵌套了2层n循环它的时间复杂度就是 O(nn)即 O(n²) 如果将其中一层循环的n改成m那它的时间复杂度就变成了 O(mn)。 代码示例
for (int i 1; i n; i) {for (int j 1; j n; j) {System.out.println(1);//该行执行了O(n²)次故O(n²)}
}立方阶O(n³) 立方阶和平方阶差不多只是多了一层循环一共有三层n循环它的时间复杂度就是O(n*n)。 代码示例
for (int i 1; i n; i) {for (int j 1; j n; j) {for (int k 1; k n; k) {System.out.println(1);//该行执行了O(n³)次故O(n³)}}
}n指数阶O(2ⁿ)
很少遇见尽量少建议少些这种复杂度的代码。
