算法:时间复杂度和空间复杂度

时间复杂度

时间复杂度指执行当前算法需要消耗的时间,这个时间并不是代码执行真正意义上的消耗时间(因为相同的算法执行的时间和测试机器的性能也有一定的关系),而是对于算法执行时间的增长变化趋势的描述。T(n) = O( f(n) );O:表示正比例关系。

常见的时间复杂度量级:

  • O( 1 ) // 常数阶
  • O( log N ) // 对数阶
  • O( n ) // 线性阶
  • O( n log N ) // 线性对数阶
  • O( n^2 ) // 平方阶
  • O( n^k ) // k方阶
  • O( 2^n ) // 指数阶

空间复杂度

空间复杂度都是指当前算法运行时需要占用的内存空间。当前这个空间并不是真的占用空间,而是一个算法在运行过程中临时占用空间大小的一个量度,同样反映的是一个趋势。S(n) = O( f(n) );

eg: 
a = [1~n];
for(i=1;i<=n;++i)
{
    j=i;
    j++;
}
// 消耗时间: (1+2n)*颗粒时间
// 时间复杂度: T(n) = O(n);
// 空间复杂度: S(n) = O(n); // 数组 a 占用 n  数量的空间;忽略了变量 i 和 j;

参考: 算法的时间与空间复杂度(一看就懂)

你要是爱学习,那我们就是好朋友。因为我也爱学习啊。哈哈哈

—— 赵钱说的

发表评论

电子邮件地址不会被公开。 必填项已用*标注