内容简介:算法是一段执行的程序, 可以理解成几行代码,或者一个方法; 算法的时间复杂度是指这段代码需要消耗的时间资源;算法的空间复杂度是指这段代码需要消耗的空间资源(空间资源通常是指占用的内存)。通常我们在讨论一个算法时会说,这个算法时间复杂度是O( ), 那个O( )。而这个O( )、O( )就是大O复杂度表示法。这个 和 具体是怎么来的呢,下面简单举个例子:上面的代码是计算 1, 2, 3… n 的和一个方法,我们假设每一行代码cpu的时间都是相同的,每一行代码执行时间为run_time, 那这段代码
算法是一段执行的程序, 可以理解成几行代码,或者一个方法; 算法的时间复杂度是指这段代码需要消耗的时间资源;算法的空间复杂度是指这段代码需要消耗的空间资源(空间资源通常是指占用的内存)。
大O复杂度表示法
通常我们在讨论一个算法时会说,这个算法时间复杂度是O( ), 那个O( )。而这个O( )、O( )就是大O复杂度表示法。这个 和 具体是怎么来的呢,下面简单举个例子:
int cal(int n) { int sum = 0; (1) for(int i = 1;i <= n; ++i){ (2) sum = sum + i; (3) } (4) return sum; } 复制代码
上面的代码是计算 1, 2, 3… n 的和一个方法,我们假设每一行代码cpu的时间都是相同的,每一行代码执行时间为run_time, 那这段代码的总执行时间 T(n) 是多少 ? 第1行为run_time, 第2行和第3行代码循环n次,时间为2 * n * run_time。所有总时间:
T(n) = (2 * n + 1)* run_time 复制代码
根据规律,可以总结成一个公式:
T(n) = O (f(n)) 复制代码
所以, 上面的O( )、O( )例子中, 以及 。 中run_time是常数, 当n足够大, 公式中的低阶、常量、系数都可以忽略不计,所有这段计算 1, 2, 3… n总和的代码时间复杂度是O( )。
常见时间复杂度有:
下面在举个空间复杂度的例子:
void print(int n){ int i = 0; (1) int[] arr = new int[n]; (2) int j = 0; (3) } 复制代码
第1行和第3行代码中都是分别申请了一个空间存储变量, 都有数据规模n无关,所有可以忽略,第2行中申请了数量为n的数组空间。所有整段代码的空间复杂度是 。
常见空间复杂度有:
掌握算法的时间复杂度与空间复杂度有什么用
首先,对比几个算法的好坏需要结合使用场景,比如数据量,内存,数据特征等。同样一段代码,在不同机器上运行速度也是不同的。通常比较几个算法的性能,就需要在同一个机器,同一批数据,同一个环境下去运行对比测试它们所需要的运行时间。
但是,但开发者是使用或者选择一个算法时,通常是没办法精准的对比算法的优劣,并且时间成本也不允许。所有我们需要一个不用具体数据来测试, 就可以粗略估算出算法的执行效率, 这就是算法的时间复杂度与空间复杂度作用啦。
最好、最坏情况时间复杂度
什么情况下,一段代码会出现有最好、最坏的情况呢; 举个例子, 比如在一个长度为n的整数数组中去找一个数,找到就立马返回数组的下表。在循环查找的过程中,最好的情况就是数组第一个就要找的,所有最好情况时间复杂度为 ; 如果数组最后一个是要找的, 这时就是最坏的情况,最坏情况时间复杂度为 。
平均情况时间复杂度
像上面一个例子,在一个长度为n的整数数组中去找一个数, 有最好和最坏情况,最好、最坏情况时间复杂度无法衡量一段代码的执行效率,这时就需要用到平均情况时间复杂度。平均=所有情况总和/总次数。
那么平均情况时间复杂度怎么算出来呢,要找的数要么在数组里,要么不在,假设在与不在的概率是 , 查找的数出现在0 ~ n-1 的位置概率是一样的,为 , 所有查找的数在数组里概率为 。总过程为:
去掉常量,复杂度为O(n)。
均摊时间复杂度
均摊时间复杂度就是一种特殊的平均时间复杂度,只能在特殊的场景才能是使用。不多说,举个例子,会 java 的对容器arraylist不陌生吧,arraylist有个默认长度的数组,add方法里,如果数组长度不够,是需要扩容的。下面以一段add方法伪代码为例:(为了代码简单易懂,以添加int为例)
int arr[] = new int[10]; //初始默认长度为10 int len = 10; int index = 0; void add(int element){ if(index >= len){ // 超出长度,数组需要扩容,并复制值到一个新数组里 final int newLen = len * 2; int new_arr[] = new int[newLen]; //申请2倍的数组 for (int i = 0; i < len; ++i){ new_arr[i] = arr[i]; } arr = new_arr; len = newLen; } arr[index] = element; ++index; } 复制代码
当不扩容时, 这个add方法时间复杂度就是 , 当扩容时, if里面复制到新数组需要遍历一次,
int arr[] = new int[10]; //初始默认长度为10 int len = 10; int index = 0; void add(int element){ if(index >= len){ // 超出长度,数组需要扩容,并复制值到一个新数组里 final int newLen = len * 2; int new_arr[] = new int[newLen]; //申请2倍的数组 for (int i = 0; i < len; ++i){ new_arr[i] = arr[i]; } arr = new_arr; len = newLen; } arr[index] = element; ++index; } 复制代码
当不扩容时, 这个add方法时间复杂度就是, 当扩容时, if里面复制到新数组需要遍历一次,
int arr[] = new int[10]; //初始默认长度为10 int len = 10; int index = 0; void add(int element){ if(index >= len){ // 超出长度,数组需要扩容,并复制值到一个新数组里 final int newLen = len * 2; int new_arr[] = new int[newLen]; //申请2倍的数组 for (int i = 0; i < len; ++i){ new_arr[i] = arr[i]; } arr = new_arr; len = newLen; } arr[index] = element; ++index; } 复制代码
当不扩容时, 这个add方法时间复杂度就是O(1), 当扩容时, if里面复制到新数组需要遍历一次,数组默认长度假设是n, 扩容时的时间复杂度是O(n)。平均情况时间复杂度是多少呢,如果像上一个例子用概率论去计算也是可以,但是麻烦。我们假设需要添加11个数,添加第11个数时需要扩容,循环10次把前10个数复制到新的数组中然后把第11个数添加进去。添加前10个数时间复杂度都是O(1), 如果把扩容时循环10次分摊到添加前10个数操作中,那么添加前10个数操作都只是都运行了一行代码而已,还是常量级别的,所有这个add方法的平均时间复杂度就是O(1)。 通过分摊分析时间复杂度就叫做均摊时间复杂度。
以上所述就是小编给大家介绍的《聊聊算法的时间复杂度与空间复杂度》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。