首页 > 其他 > 详细

时间复杂度与空间复杂度

时间:2020-07-01 12:34:39      阅读:32      评论:0      收藏:0      [点我收藏+]

时间复杂度与空间复杂度是算法中的概念。
时间复杂度T(n) = O(f(n))=>T(Time);O(这里是大写字母O,并不是用于来真实代表算法的执行时间,而是用来表示代码执行时间的增长变化趋势);n(代表影响复杂度的因子); f(n)代表复杂度的具体算法
空间复杂度S(n) = O(f(n))=>S(Space)
所谓时间复杂度,就是算法的运算时间,通过代码的执行次数来表示。
所谓空间复杂度,就是算法在运算过程中占用的临时空间。

常见的时间复杂度量级:
①常数阶 O(1)

int a = 11;
int b = 22;

这就是常见的变量定义,上面的代码执行时间并不会随着某个变量的增长而增长,因此复杂度就是O(1)。

②线性阶O(n)

for(int i = 0;i<n;i++){
      a++;
}

循环体内的每一行代码都会执行n次,此算法的复杂度为O(n).

③对数阶O(logn)

while(a<n){
a = a*2;
}

每次循环都会*2,因此总共的循环次数为log2n,但因为n数据规模才是影响复杂度的关键,因此忽略底数,复杂度为O(logn)

④线性对数阶O(nlogn)

for(int i = 0;i<n;i++){
      while(a<n){
      a = a*2;
}

这里就是将复杂度为O(logn)的代码循环执行n次。

⑤平方阶O(n2)

for(int i = 0;i<n;i++){
   for(int j = 0;j<n;j++){
      a++;
   }   
}

这里将复杂度为O(n)的代码再嵌套循环一遍,时间复杂度就是 O(n2)了。

立方阶O(n3) K次方阶O(n^k) 与平方类似,几次方就嵌套循环几次。

空间复杂度
①O(1)

int x = 1;
int y = 2;

上面,分配的内存空间不变的,就是O(1)

②O(n)
int[] arr = new int[n];
上面,分配的内存空间会随着n改变的,就是O(n)

时间复杂度与空间复杂度

原文:https://www.cnblogs.com/bemad/p/13218345.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!