百度权重站长工具,wordpress添加备案号插件,黑龙江住房和城乡建设厅网站首页,专门做h5的网站目录 前言一、时间复杂度1.1 时间复杂度公式1.2 常见的时间复杂度量级1.3 时间复杂度量级示例1.3.1 常数阶O(1)1.3.2 对数阶O(logN)1.3.3 线性阶O(n)1.3.4 线性对数阶O(nlogN)1.3.5 平方阶O(n)1.3.6 立方阶O(n)、K次方阶O(n^k) 二、空间复杂度2.1 O(1)2.2 O(n)2.3 O(n) 三、常用… 目录 前言一、时间复杂度1.1 时间复杂度公式1.2 常见的时间复杂度量级1.3 时间复杂度量级示例1.3.1 常数阶O(1)1.3.2 对数阶O(logN)1.3.3 线性阶O(n)1.3.4 线性对数阶O(nlogN)1.3.5 平方阶O(n²)1.3.6 立方阶O(n³)、K次方阶O(n^k) 二、空间复杂度2.1 O(1)2.2 O(n)2.3 O(n²) 三、常用算法的时间复杂度3.1 O(1)相关算法3.2 O(logn)相关算法3.3 O(n)相关算法3.4 O(nlogn)相关算法3.5 O(n^ 2)相关算法 前言
算法是一组用于操作数据和解决问题的方法。尽管不同算法在解决同一问题时可能得到相同结果但它们在资源消耗和执行时间上可能存在显著差异。 评估不同算法的优劣应主要考虑时间和空间两个维度。 时间维度指算法执行所需的时间通常用时间复杂度描述。 空间维度指算法执行所需的内存空间通常用空间复杂度描述。 评估算法效率的关键在于其时间复杂度和空间复杂度。然而有时时间和空间是一种取舍的关系需要在二者之间取得平衡。
一、时间复杂度
评估算法的时间复杂度时许多人可能首先考虑运行算法程序并测量其消耗的时间。尽管这种方法可行但存在一些缺点。 这种方法容易受到运行环境的影响在性能较高的计算机上运行的结果可能与在性能较低的计算机上运行的结果有很大差异。此外测试数据规模对结果也有重要影响。另外在编写算法时可能无法完全运行算法。 因此另一种更通用的方法是使用「大O符号表示法」即 T(n) O(f(n))来描述算法的时间复杂度。
1.1 时间复杂度公式
时间复杂度的公式是 T(n) O( f(n) ) 有关此公式的解释如下 其中f(n) 表示每行代码执行次数之和而 O 表示正比例关系这个公式的全称是算法的渐进时间复杂度。去简化:大O符号表示法并不是用于来真实代表算法的执行时间的它是用来表示代码执行时间的增长变化趋势的。 去简化示例
for(i1; in; i) //第1行
{ //第2行 j i; //第3行 j; //第4行
} //第5行 假设每行代码的执行时间都是一样的用 1s来表示那么 这个例子的第一行耗时是1s时间 第三行的执行时间是 ns时间 第四行的执行时间也是 ns时间第二行和第五行是符号暂时忽略 那么总时间就是 1s时间 ns时间 ns时间 即 (12n)s个时间即 T(n) (12n)s 时间 可以看出这个算法的耗时是随着n的变化而变化因此如果n无限大的时候T(n) time(12n)中的常量1就没有意义了倍数2也意义不大。因此直接简化为T(n) O(n) 就可以了。 1.2 常见的时间复杂度量级 常数阶O(1) 对数阶O(logN) 线性阶O(n) 线性对数阶O(nlogN) 平方阶O(n²) 立方阶O(n³) K次方阶O(n^k) 指数阶(2^n) 上面从上至下依次的时间复杂度越来越大执行的效率越来越低。
1.3 时间复杂度量级示例
1.3.1 常数阶O(1)
无论代码执行了多少行只要是没有循环等复杂结构那这个代码的时间复杂度就都是O(1)如
int i 1;
int j 2;
i;
j;
int m i j;上述代码在执行的时候它消耗的时候并不随着某个变量的增长而增长那么无论这类代码有多长即使有几万几十万行都可以用O(1)来表示它的时间复杂度。 1.3.2 对数阶O(logN)
看代码
int i 1;
while(in)
{i i * 2;
}可以看到在while循环里面每次都将 i 乘以 2乘完之后i 距离 n 就越来越近了。我们试着求解一下假设循环x次之后i 就大于 2 了此时这个循环就退出了也就是说 2 的 x 次方等于 n那么 x log2^n 也就是说当循环 log2^n 次以后这个代码就结束了。因此这个代码的时间复杂度为O(logn) 1.3.3 线性阶O(n)
如
for(i1; in; i)
{j i;j;
}for循环里面的代码会执行n遍因此它消耗的时间是随着n的变化而变化的因此这类代码都可以用O(n)来表示它的时间复杂度。 1.3.4 线性对数阶O(nlogN)
线性对数阶O(nlogN) 其实非常容易理解将时间复杂度为O(logn)的代码循环N遍的话那么它的时间复杂度就是 n * O(logN)也就是了O(nlogN)。
for(m1; mn; m)
{i 1;while(in){i i * 2;}
}1.3.5 平方阶O(n²)
平方阶O(n²) 更容易理解了如果把 O(n) 的代码再嵌套循环一遍它的时间复杂度就是 O(n²) 了。 举例
for(x1; in; x)
{for(i1; in; i){j i;j;}
}这段代码其实就是嵌套了2层n循环它的时间复杂度就是 O(n*n)即 O(n²) 如果将其中一层循环的n改成m即
for(x1; im; x)
{for(i1; in; i){j i;j;}
}那它的时间复杂度就变成了 O(m*n)
1.3.6 立方阶O(n³)、K次方阶O(n^k)
参考上面的O(n²) 去理解O(n³)相当于三层n循环其它的类似。 二、空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度记做S(n)O(f(n))。 空间复杂度比较常用的有O(1)、O(n)、O(n²)
2.1 O(1)
空间复杂度为O(1)的示例
public void printNumber(int number) {System.out.println(number);
}在这个示例中无论输入的数字是多少该函数只需要固定的空间来存储一个数字的内存空间因此空间复杂度为O(1)。
2.2 O(n)
空间复杂度为O(n)的示例
public void printNumbers(int[] numbers) {for (int i 0; i numbers.length; i) {System.out.println(numbers[i]);}
}在这个示例中函数接收一个整型数组作为参数然后遍历整个数组并打印每个元素。随着输入数组大小的增加需要存储的元素数量也相应增加因此空间复杂度为O(n)。
2.3 O(n²)
空间复杂度为O(n²)的示例
public void printMatrix(int[][] matrix) {for (int i 0; i matrix.length; i) {for (int j 0; j matrix[i].length; j) {System.out.print(matrix[i][j] );}System.out.println();}
}在这个示例中函数接收一个二维整型数组作为参数然后遍历整个二维数组并打印每个元素。由于有两层嵌套循环随着输入二维数组的大小增加需要存储的元素数量将呈二次方增长因此空间复杂度为O(n²)
三、常用算法的时间复杂度
3.1 O(1)相关算法
O(1)就是最低的时空复杂度了也就是耗时/耗空间与输入数据大小无关无论输入数据增大多少倍耗时/耗空间都不变。 哈希算法就是典型的O(1)时间复杂度无论数据规模多大都可以在一次计算后找到目标不考虑冲突的话
3.2 O(logn)相关算法
比如O(logn)当数据增大n倍时耗时增大logn倍这里的log是以2为底的比如当数据增大256倍时耗时只增大8倍是比线性还要低的时间复杂度。二分查找就是O(logn)的算法每找一次排除一半的可能256个数据中查找只要找8次就可以找到目标。
3.3 O(n)相关算法
时间复杂度为O(n)就代表数据量增大几倍耗时也增大几倍。比如常见的遍历算法。
3.4 O(nlogn)相关算法
O(nlogn)同理就是n乘以logn当数据增大256倍时耗时增大256*82048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。
3.5 O(n^ 2)相关算法
再比如时间复杂度O(n^ 2)就代表数据量增大n倍时耗时增大n的平方倍这是比线性更高的时间复杂度。比如冒泡排序就是典型的O(n^2)的算法对n个数排序需要扫描n×n次。
参考链接 算法的时间与空间复杂度一看就懂
