Login light

https://www.jianshu.com/p/f4cca5ce055a

算法复杂度

算法复杂度分为时间复杂度空间复杂度

时间复杂度

一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。
一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)

渐进时间复杂度

有了基本操作执行次数的函数 T(n),是否就可以分析和比较一段代码的运行时间了呢?还是有一定的困难。
比如算法A的相对时间是T(n)= 100n,算法B的相对时间是T(n)= 5n^2,这两个到底谁的运行时间更长一些?这就要看n的取值了。
所以,这时候有了渐进时间复杂度(asymptotic time complexity)的概念,官方的定义如下:
若存在函数 f(n),使得当n趋近于无穷大时,T(n)/ f(n)的极限值为不等于零的常数,则称 f(n)T(n)的同数量级函数。
记作 T(n)= O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
渐进时间复杂度用大写O来表示,所以也被称为大O表示法。

推导时间复杂度

  1. 如果运行时间是常数量级,用常数1表示;
  2. 只保留时间函数中的最高阶项;
  3. 如果最高阶项存在,则省去最高阶项前面的系数。

例:
场景1:
T(n) = 3n
最高阶项为3n,省去系数3,转化的时间复杂度为:
T(n) = O(n)

场景2:
T(n) = 5logn
最高阶项为5logn,省去系数5,转化的时间复杂度为:
T(n) = O(logn)

场景3:
T(n) = 2
只有常数量级,转化的时间复杂度为:
T(n) = O(1)

场景4:
T(n) = 0.5n^2 + 0.5n
最高阶项为0.5n^2,省去系数0.5,转化的时间复杂度为:
T(n) = O(n^2)