复杂度分析

大O复杂度表示法

所有代码的执行时间 T(n) 与每行代码的执行次数

def cal (n)
  sum = 0
  for i in 1..nu
    sum += i
  end
  return sum
end

粗略估计该方法的时间复杂度：

将每行代码的执行时间都设为 1u ，第2行代码需要 1u ，第3，4代码（for循环）运行了N次，这段代码的总执行时间就是(2n+1)*u。

我们可以得出，所有代码的执行时间T(n)与每行代码的执行次数成正比。

def cal(n)
  sum = 0
for i in 0..n
  j = 1
    for j in 0..n
        sum = sum + i*j
    end
end
    return sum
end

再看一下该函数

同样假设每行代码的执行时间都为 1u ,第2行需要1u ，第3，4行执行N次也就是 2n*u,第5，6行执行了 N²次，所以整段代码执行的总时间为：(2n²+2n+1)*u

通过这两段代码可以推出一个重要结论：

所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比

T(n) = O(f(n))

• T(n)表示代码执行的时间；
• n 表示数据规模的大小；
• f(n) 表示每行代码执行的次数总和。
• 因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

当N的数量级很大的时候，公式中的常数、系数和低阶表达式都是可以忽略的，只需要考虑最大量级即可，随意刚刚的两个表达式也可以写为T(n) = O(n), T(n) = O(n²)。

时间复杂度分析

只关注循环执行次数最多的一段代码

我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。所以，我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度。

加法法则：总复杂度等于量级最大的那段代码的复杂度

def cal(int n) 
   # yield 1
   sum_1 = 0
   p = 1
   for p in 0..100
     sum_1 = sum_1 + p
   end
  
 # yield 2
   sum_2 = 0
    q = 1
   for q in 0..n
     sum_2 = sum_2 + q
   end
  
 # yield 3
   sum_3 = 0
   i = 1
   j = 1
   for i in i..n
     j = 1;
     for j in j..n
        sum_3 = sum_3 +  i * j
       end
     end
 
   return sum_1 + sum_2 + sum_3;
  end

该函数分为三部分，分别是求sum_1、sum_2、sum_3，分析每一部分的复杂度再去最大的量级作为整个函数的复杂度。

在上面提到过，当N达到无限大的时候，一段代码的复杂度，是按照最大量级来取的，就是说只需要关注这个段代码中最复杂的部分，也就是 yield 3

yield 3的复杂度为O(n²)

所以得出结论

总的时间复杂度就等于量级最大的那段代码的时间复杂度

乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

简单来讲乘法法则就是嵌套循环，拿之前的一个例子来讲：

def cal(n)
  sum = 0
  
for i in 0..n
  j = 1
    for j in 0..n
        sum = sum + i*j
    end
end
  
    return sum
end

外层循环的复杂度是 n，内层循环的复杂度也是n，所以该函数的复杂度为 n*n即n²。

几种常见时间复杂度的实例分析

常见的复杂度量级如下,按数量级递增：

• 常数级 O(1)
• 对数级O(logn)
• 线性级O(n)
• 线性对数级O(nlogn)
• 平方级O(n²) 立方级 O(n³)…
• 指数级O(2∧n)
• 阶乘级O(n!)

对于刚罗列的复杂度量级，我们可以粗略地分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2n) 和 O(n!)。

O(1)

O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如这段代码，即便有 3 行，它的时间复杂度也是 O(1），而不是 O(3)

i = 1
j = 2
sum = i + j

只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。或者说，一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。

O(logn)、O(nlogn)

i = 1
while i < n do
  i = i*2
end

第三行代码是执行最多次的，我们只需要计算该代码执行了多少次，就可以看出整段代码的复杂度：

2^k = n

所以我们只需要知道k的值 就可以知道整块代码的复杂度：

k = log₂n

即复杂度为O(log₂n)

同样的在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))

当N趋于无限大时，对数的大小可以忽略底数，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。

如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。

O(m+n)、O(m*n)

代码的复杂度由两个数据的规模来决定

sum_1 = 0
p = 1
for p in 0..100
  sum_1 = sum_1 + p
end

sum_2 = 0
q = 1
for q in 0..m
  sum_2 = sum_2 + q
end

m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 O(m+n)

空间复杂度分析

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。

类比一下，

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

常见的空间复杂度就是 O(1)、O(n)、O(n2 )，即程序运行和数据空间之间的关系

info = Array.new(n)

该代码的空间复杂度就是n

---