聊聊算法的时间复杂度与空间复杂度

栏目: 编程工具 · 发布时间: 5年前

内容简介:算法是一段执行的程序, 可以理解成几行代码,或者一个方法; 算法的时间复杂度是指这段代码需要消耗的时间资源;算法的空间复杂度是指这段代码需要消耗的空间资源(空间资源通常是指占用的内存)。通常我们在讨论一个算法时会说,这个算法时间复杂度是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)。 通过分摊分析时间复杂度就叫做均摊时间复杂度。


以上所述就是小编给大家介绍的《聊聊算法的时间复杂度与空间复杂度》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Haskell

Haskell

Simon Thompson / Addison-Wesley / 1999-3-16 / GBP 40.99

The second edition of Haskell: The Craft of Functional Programming is essential reading for beginners to functional programming and newcomers to the Haskell programming language. The emphasis is on th......一起来看看 《Haskell》 这本书的介绍吧!

html转js在线工具
html转js在线工具

html转js在线工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具