前言:
今天朋友们对“大o 算法”大概比较看重,大家都想要分析一些“大o 算法”的相关知识。那么小编在网摘上汇集了一些对于“大o 算法””的相关知识,希望大家能喜欢,各位老铁们快快来学习一下吧!做了这么多年的程序员,是不是一直靠着自己的聪明伶俐在编码,数据结构和算法是前辈们的心血和经验总结,不可错过。
数据结构是利用其存储结构和逻辑结构来有效地组织数据,比如线性的表、栈、队列,非线性的树、图等,而算法是描述运算的过程,良好的算法是建立在有效的数据结构之上的。
评价算法的指标
评价一个算法的好坏,除了他正确性指标外,就是所消耗的时间和空间。
为了方便计算所消耗的时间,需要先作2个假设:
算法与计算机的软硬件无关(硬件好理解,软件比如编程语言、执行器、编译器等);代码中的每个语句所消耗的时间都一样,记作一个时间单位;
举个例子
for (int i = 0; i < n; i++) { //① for (int j = 0; j < n; j++) { //② c[i][j] = 0; //③ for (int k = 0; k < n; k++) { //④ c[i][j] = a[i][k] + b[k][j] + c[i][j]; //⑤ } }}
计算它所消耗时间的过程如下
语句①需要循环到i=n时才会完结,所以它耗费n+1个时间单位;语句②同语句①,自己的的循环中耗费n+1个时间单位,但它在①的n次循环体内,所以消耗n*(n+1)个时间单位;语句③在语句①②循环体内,它们分别循环n次,所以语句③消耗n*n个时间单位;语句④同③,但它本身执行n+1,所以语句④消耗n*n*(n+1)个时间单位;语句⑤在语句①②④循环体内,它消耗n*n*n个时间单位;
所以总体消耗的时间为:n+1 + n*(n+1) + n*n+n*n*(n+1)+n*n*n=2n3+3n2+2n+1;
算法的时间复杂度
上例最终消耗的时间可以用函数表示:T(n)=2n3+3n2+2n+1,但用这么长的算式评价算法的好坏过于繁冗。实际上它是变量n的函数,表示随着n的增大影响着T(n)的增长率变化,化繁为简可进一步抽象为n的量级函数:T(n)=O(f(n)。T(n)=2n3+3n2+2n+1的最大量级是n3,因此可简化为T(n)=O(n3),这就大O表示法。
计算机科学经常用大O表示算法的复杂度或衡量性能,它主要用于描述在最坏的情况下所花费的时间和空间(内存或磁盘)。
为了更形象,下面列举几个例子,根据计算消耗时间的方法很容易得出结果。
O(1)
O(1)表示算法的执行总是消耗相同的时间,比如
boolean isFirstElementEmpty(List<String> elements){ return elements.get(0).isEmpty();}O(n)
O(n)表示算法的复杂度是线性增长的,与数据集的大小成正比。
boolean ContainsValue(List<String> elements, String value) { for (String element : elements) { if (element.equals(value)) return true; } return false;}
如果不用foreach,使用for会更直观些
boolean ContainsValue(List<String> elements, String value) { int n = elements.size(); for (int i = 0; i < n; i++) { if (elements.get(i).equals(value)) return true; } return false;}
它是消耗时间单位算式是1+n+1+n+1=2n+3,根据n的量级简化为大O表示即O(n)。
O(n2)
O(n2)表示算法的复杂度与数据集大小的平方成正比,一般的循环嵌套就是这种,随着嵌套的层级增加可能是O(n3)、O(n4)等。
boolean ContainsDuplicates(List<String> elements) { for (int i = 0; i < elements.size(); i++) { for (int j = 0; j < elements.size(); j++) { if (i == j) continue; if (elements.get(i).equals(elements.get(j))) return true; } } retrn false;}O(2n)
O(2n)表示算法的复杂度与数据集大小成指数增长,比如递归
int Fibonacci(int number) { if (number <= 1) return number; return Fibonacci(number - 2) + Fibonacci(number - 1);}O(log2n)指数复杂度
二分法查找时间复杂度最好的情况是O(1),最坏的情况根据Master定理T(n)=T(n/2)+O(1),所以是O(log2n)。它的原理是对于已经排序的数据集,先取中间值进行对比,成功即返回否则根据对比结果确定下一次的中间值对比,依次类推
int binarySearch(int[] arr, int value) { int start = 0, end = arr.length - 1; while (start <= end) { int middle = (start + end) / 2; if (value == arr[middle]) { return middle; } if (value > arr[middle]) { start = middle + 1; } if (value < arr[middle]) { end = middle - 1; } } ren -1;}算法空间的复杂度
空间的复杂度的计算方法和时间复杂度一样,只是这里假设算法的指令、常数、变量和输入数据用到的寄存器相同,而只计算其用到的辅助空间单元个数。
实际上时间和空间是一对矛盾的冤家,一般情况下要么拿时间换空间,要么拿空间换时间,鱼和熊掌不可兼得。
复杂度对比
算法的复杂度一般从小到大顺序依次是O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n)
百万并发「零拷贝」技术系列之经典案例Netty
千万不能让程序员给娃娃取名字
一口气讲透一致性哈希(Hash),助力「码农变身」
漫画 | 架构设计中的那些事
接住喽,送你个装B的技能:JDK动态代理
Intellij IDEA必备插件,提高效率的“七种武器”
Java中异常处理的9个最佳实践
标签: #大o 算法 #算法o #二分法最差时间复杂度